Home > graph theory, Sage > Algorithmic graph theory book 0.3 released

Algorithmic graph theory book 0.3 released

I’m delighted to announce the release of version 0.3 of the book Algorithmic Graph Theory. You can grab the latest release of the book at the project website on Google Code.

Initially, I started writing that book in November 2009 as a way to document the graph theory module of Sage. In the process, I discovered two bugs (cf. #8372 and #8395). In January 2010, David Joyner began contributing to the book, resulting in the release of version 0.2 on 26th January 2010. Recently, Nathann Cohen contributed a chapter to the book. And with David’s latest patch, a first draft of the chapter on trees and forests is complete.

Notable changes in version 0.3 include:

  • A first draft of the chapter “Trees and Forests”.
  • Polishing up the chapter “Introduction to Graph Theory”. The majority of the tikz/pgf macros of this chapter have been rewritten to make them more compact.
  • A first draft of the chapter “Graph Problems and Their LP Formulations”.
  • Fix typos reported by Fidel Barrera-Cruz and Daniel Black.

A big thank you to Fidel and Daniel.

  1. dorkusmonkey
    19 March 2010 at 4:33 pm

    whoa, graph isomorphism does _not_ have such a simple algorithm. This is still an open problem. I wish I could whip up a counter example quickly and easily but the burden of proof should fall to you. I believe you’ll find some counter examples with graphs that have high eigenvalue multiplicity, but thats just intuition.

    Please see http://en.wikipedia.org/wiki/Graph_isomorphism_problem and the related http://en.wikipedia.org/wiki/Graph_automorphism_problem .

  2. 20 March 2010 at 1:58 am

    I don’t know about that. I kind of doubt it.

  3. Bob Foster
    21 March 2010 at 9:00 pm

    @dorkusmonkey According to the Wikipedia article, there are algorithms that solve the problem in exponential time. Nothing says that there cannot be an easy to state exponential algorithm, though this one is sort of an exercise for the reader. A better criticism is: the book doesn’t comment on complexity. What sort of book on algorithms ignores complexity?

  1. 19 March 2010 at 11:30 am
  2. 19 March 2010 at 2:23 pm
  3. 19 March 2010 at 3:10 pm
  4. 20 March 2010 at 12:10 am
  5. 20 March 2010 at 2:08 pm

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: