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.

Categories: graph theory, Sage
1. 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.

2. 20 March 2010 at 1:58 am

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

3. 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