Looking for a book on graph algorithms
I'm looking for a good book on graph algorithms, perhaps something a bit different than the usual introductory book. For example, I would like an algorithm for finding all paths from vertex v to vertex u, not necessarily the shortest one or the longest one. Also, algorithms for determining the girth, diameter, and other properties of graphs are of interest. Or perhaps I should be looking at journal papers? Any pointers will be appreciated. Roger House
On Fri, Jan 23, 2009 at 12:15 PM, Roger House <rhouse@sonic.net> wrote:
I'm looking for a good book on graph algorithms, perhaps something a bit different than the usual introductory book. For example, I would like an algorithm for finding all paths from vertex v to vertex u, not necessarily the shortest one or the longest one. Also, algorithms for determining the girth, diameter, and other properties of graphs are of interest. Or perhaps I should be looking at journal papers? Any pointers will be appreciated.
I'm not sure about books on graph algorithms, and (in my experience) journal papers on graph algorithms aren't generally geared towards implementers. There are algorithms in sandbox/SOC/2007/graphs that compute girth, diameter, and several other measures. They were supposed to be integrated into the trunk pending a mini-review, but it never happened. I may try to decouple from them the SoC changes to the library and add them to the trunk, but I probably won't have time for a while. Andrew Sutton andrew.n.sutton@gmail.com
I'm assuming you've already checked CLR and Aho, Hopcroft, and Ullman? They don't solve the specific problems you mention but are a always good starting point. If you really want up-to-date algorithms, I disagree with Andrew, Conference/Journal papers are exactly where you should look. If you're looking for things like girth, diameter, etc. the Infovis community might have some useful resources as they're always interested in properties of networks. There are a lot of books on graph algorithms out there but I haven't found most of them particularly useful. When I look at implementing new algorithms in the Parallel BGL I check the above resources, plus Ja Ja (An Introduction to Parallel Algorithms), then head straight for conferences/journal publications. With regards to finding all paths from v to u, you can modify the BGL's implementation of Dijkstra's algorithm to relax equal-weight edges fairly simply (or you could just check for equal weight edges on non-tree-edge which makes figuring out when to terminate easier). Then if you make all edges have weight 0 (just replace your edge weight property map with one that always returns 0) all paths will be equal weight and you'll be able to identify all paths from v to u. Cheers, Nick On Jan 23, 2009, at 12:27 PM, Andrew Sutton wrote:
On Fri, Jan 23, 2009 at 12:15 PM, Roger House <rhouse@sonic.net> wrote: I'm looking for a good book on graph algorithms, perhaps something a bit different than the usual introductory book. For example, I would like an algorithm for finding all paths from vertex v to vertex u, not necessarily the shortest one or the longest one. Also, algorithms for determining the girth, diameter, and other properties of graphs are of interest. Or perhaps I should be looking at journal papers? Any pointers will be appreciated.
I'm not sure about books on graph algorithms, and (in my experience) journal papers on graph algorithms aren't generally geared towards implementers.
There are algorithms in sandbox/SOC/2007/graphs that compute girth, diameter, and several other measures. They were supposed to be integrated into the trunk pending a mini-review, but it never happened. I may try to decouple from them the SoC changes to the library and add them to the trunk, but I probably won't have time for a while.
Andrew Sutton andrew.n.sutton@gmail.com _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
Cormen, Leiserson, and Rivest http://www.amazon.com/Introduction-Algorithms-Thomas-H-Cormen/dp/0262032937/ref=sr_1_1?ie=UTF8&s=books&qid=1232750104&sr=8-1 On Jan 23, 2009, at 5:24 PM, Thomas Klimpel wrote:
Nick Edmonds wrote:
I'm assuming you've already checked CLR and Aho, Hopcroft, and Ullman? They don't solve the specific problems you mention but are a always good starting point.
CLR ??? <winmail.dat>_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
On Fri, Jan 23, 2009 at 3:36 PM, Nick Edmonds <ngedmond@cs.indiana.edu>wrote:
Cormen, Leiserson, and Rivest
CLRS is the current version. Stein is now a co-author. Jon
On Jan 23, 2009, at 7:20 PM, Jonathan Franklin wrote:
On Fri, Jan 23, 2009 at 3:36 PM, Nick Edmonds <ngedmond@cs.indiana.edu> wrote: Cormen, Leiserson, and Rivest
CLRS is the current version. Stein is now a co-author.
Yep, my copy has Stein as a co-author, but I still refer to it as CLR, apologies to Stein. -Nick
Jon
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
On Mon, Jan 26, 2009 at 12:34 PM, Nick Edmonds <ngedmond@cs.indiana.edu>wrote:
Yep, my copy has Stein as a co-author, but I still refer to it as CLR, apologies to Stein.
Yeah, in the popular CS jargon, CLR refers to the first edition, and CLRS to the second. http://en.wikipedia.org/wiki/CLRS Currently, my favorite algorithms book. Jon
On Fri, Jan 23, 2009 at 09:15:48AM -0800, Roger House wrote:
For example, I would like an algorithm for finding all paths from vertex v to vertex u, not necessarily the shortest
http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/ http://www.cs.berkeley.edu/~vazirani/algorithms.html
On Fri, Jan 23, 2009 at 12:09 PM, Zeljko Vrba <zvrba@ifi.uio.no> wrote:
On Fri, Jan 23, 2009 at 09:15:48AM -0800, Roger House wrote:
For example, I would like an algorithm for finding all paths from vertex v to vertex u, not necessarily the shortest
http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/
The Diestel book, and the _Algorithmic Graph Theory_ book that I recommended are both good texts, but may be more graph theoretical than you're looking for. But they're both worth a look. Here's a google books link for the AGT book that you can preview: http://books.google.com/books?id=5IV5elVucSwC&printsec=frontcover&dq=editions:ISBN0444515305#PPP1,M1 Jon
On Fri, Jan 23, 2009 at 10:15 AM, Roger House <rhouse@sonic.net> wrote:
I'm looking for a good book on graph algorithms, perhaps something a bit different than the usual introductory book. For example, I would like an algorithm for finding all paths from vertex v to vertex u, not necessarily the shortest one or the longest one. Also, algorithms for determining the girth, diameter, and other properties of graphs are of interest. Or perhaps I should be looking at journal papers? Any pointers will be appreciated.
I like _Algorithmic Graph Theory_ by Golumbic. The CLRS, which someone else already mentioned also has a few graph algorithms. There are many others. Jon
participants (6)
-
Andrew Sutton -
Jonathan Franklin -
Nick Edmonds -
Roger House -
Thomas Klimpel -
Zeljko Vrba