Algorithms on Trees and Graphs [Hardcover]

Gabriel Valiente (Author)

Book Description

Publication Date: October 28, 2002

Graph algorithms is a well-established subject in mathematics and computer science. Beyond classical application fields, such as approximation, combinatorial optimization, graphics, and operations research, graph algorithms have recently attracted increased attention from computational molecular biology and computational chemistry. Centered around the fundamental issue of graph isomorphism, this text goes beyond classical graph problems of shortest paths, spanning trees, flows in networks, and matchings in bipartite graphs. Advanced algorithmic results and techniques of practical relevance are presented in a coherent and consolidated way. This book introduces graph algorithms on an intuitive basis followed by a detailed exposition in a literate programming style, with correctness proofs as well as worst-case analyses. Furthermore, full C++ implementations of all algorithms presented are given using the LEDA library of efficient data structures and algorithms.

Editorial Reviews

Review

From the reviews:

"The main theme of this (research) monograph on graph algorithms is the isomorphism problem (for trees and graphs). Algorithms are both described on an intuitive basis and presented (and discussed) in detail using Knuth’s literate programming style (C++, using the LEDA library). Besides offering an introduction to an interesting and important subject (with applications, e.g., in biology and chemistry), it also is a valuable (and unified) reference to material previously only available in research papers." (P. Schmitt, Monatshefte für Mathematik, Vol. 142 (4), 2004)

"The book goes beyond classical graph problems and addresses algorithmic problems with practical applications. … will have a great potential in the hands of a dedicated teacher who is both willing and capable of using the software. Because much of the material in the book was previously only available in specialized research literature, this book will be very valuable also for researchers of algorithmic graph theory. This richly illustrated book has an extensive bibliography and several appendices describing the software." (Matti Vuorinen, Zentralblatt MATH, Vol. 1007, 2003)

From the Back Cover

Graph algorithms is a well-established subject in mathematics and computer science. Beyond classical application fields, like approximation, combinatorial optimization, graphics, and operations research, graph algorithms have recently attracted increased attention from computational molecular biology and computational chemistry. Centered around the fundamental issue of graph isomorphism, this text goes beyond classical graph problems of shortest paths, spanning trees, flows in networks, and matchings in bipartite graphs. Advanced algorithmic results and techniques of practical relevance are presented in a coherent and consolidated way. This book introduces graph algorithms on an intuitive basis followed by a detailed exposition in a literate programming style, with correctness proofs as well as worst-case analyses. Furthermore, full C++ implementations of all algorithms presented are given using the LEDA library of efficient data structures and algorithms. Numerous illustrations, examples, and exercises, and a comprehensive bibliography support students and professionals in using the book as a text and source of reference

Product Details

• Hardcover: 450 pages
• Publisher: Springer; 1 edition (October 28, 2002)
• Language: English
• ISBN-10: 3540435506
• ISBN-13: 978-3540435501
• Product Dimensions: 9.4 x 6.5 x 1.2 inches
• Shipping Weight: 1.9 pounds (View shipping rates and policies)
• Average Customer Review: 3.7 out of 5 stars  See all reviews (3 customer reviews)
• Amazon Best Sellers Rank: #1,377,455 in Books (See Top 100 in Books)

More About the Author

Discover books, learn about writers, read author blogs, and more.

Customer Reviews

Most Helpful Customer Reviews

33 of 33 people found the following review helpful:

4.0 out of 5 stars Intersting Studies Hampered by LEDA and LP Dependencies, December 23, 2003

By 

Mike Blaszczak (Mercer Island, WA, USA) - See all my reviews
(REAL NAME)   

Amazon Verified Purchase

This review is from: Algorithms on Trees and Graphs (Hardcover)

I'm pleased with the text in this book; the descriptions are almost all clear, and reading through the book gives me insight into some more interesting problems in trees and graphs. The high points of the book are its treaments of tree and graph isomorphism, but I also found the discussions of non-traditional traversal algorithms on trees and graphs very interesting. The author discussions leaf-first, breadth-first, and depth-first traversals and provides algorithms for their implementation. Many of the algorithms include correctness proofs.

These topics alone made the book worth its to me. A deep academic book that costs less than $50 is nearly unheared-of.

Unfortunately, there are two flaws that make the book hard to use. In a nutshell, the author expects the reader to buy into a couple of pretty invasive and expensive propositions.

First, the author decided to use literate programming for all of his presented algorithms and code fragments. This isn't so bad, since literate programming is about documenting code. If you suppose that the author wrote the code, then documented it, then calld it a book, using a tool like literate programming seems like a natural choice.

But if you're not familiar with literate programming, it's a bit of a chore. The author's introduction to literate programming doesn't help with some of the questions even an experienced programmer might have wend reading the text. More practically, literate programming enforces operators that are different than most C/C++ developers are familiar with, and can cause confusion when reading the text. ^ is used, for example, to indicate a logical and, where C/C++ developers expect it to indicate a bitwise-exclusive or.

While it's esay to eventually overcome such tricks of memory, I've been finding it hard to scan literate programs to find definitions and declarations. The author doesn't include a CD (and at this cover price, that is hard to fault) but also doesn't make his code available for download. His website includes a LEDA-based program that interactively demonstrates some algorithms, but doesn't include code for the algorithm his own books develops and discusses.

The other decision made by the author, to the overwhelming inconvenience of this reader, is the reliance on the LEDA library for his samples and programs. The algorithms are understandable without the library, but a reader without access to LEDA doesn't benefit from any of the visualizations the author provides. , and several include

In fact, the author spends about 40 pages discussing LEDA and the characteristics of its implementation. Maybe researchers working on tree and graph algorithms all use LEDA and have ready access to it, but the literate programming code provided to for some of the algorithms isn't useful to readers who aren't familiar with LEDA, as researching the definitions and declarations themsleves becomes arduous.

The bibliography is very diverse, with more than 380 entries and is well-cited throughout the book. Unfortunately, the author sometimes relies on the bibliography too much. On page 392, the author brings up "the so-called graph isopomorphism disease" without defining it himself; he instead relies on his bibliography entries to give the user any definition or background on the "disease".

Unfortunately, the index received not nearly as much attention as the bibliography; neglecting whitespace, it's scarcely more than a single page long!

The book appears to be something more than a research paper, but is written much like a research apper would be. The book probably also serves well for a class that teaches this subject, and assumes LEDA and literate programming as prerequisites. But as a commercial developer who's interested in applying advanced graph and tree algorithms to the work I'm doing, I found the book has limited its value by relying on LEDA and applying literate programming.

All this said, I still feel it's appropriate to give the book four stars. The material covered is hard to find elsewhere, and with some effort I can overcome the LEDA and literate programming hurdles. Since I don't use LEDA or literate programming day-to-day, I'll have to overcome that unfamiliarity every time I pick up the book as a reference.

3 of 3 people found the following review helpful:

4.0 out of 5 stars Book centered entirely on combinatorial subgraph problems, June 1, 2009

By 

Digital Puer "digital_puer" (Los Angeles, CA USA) - See all my reviews

This review is from: Algorithms on Trees and Graphs (Hardcover)

This book's title is very misleading, as the author's focus really is on subgraph problems (e.g. subgraph and tree isomorphism, clique, independent set, and vertex cover).

The book barely mentions other graph theory topics such as distance algorithms (e.g. single-source shortest path, minimum-spanning tree, transitive closure), network flow, or graph colouring. This odd focus is really frustrating since the author spends a large number of pages on relatively simple topics such as tree traversal (34 pages on things like pre-order traversal) and graph traversal (42 pages on things like depth-first search). In fact, in section 5.3 on graph traversal applications, the author suggests that the reader may have already learned about algorithms such as shortest path or topological sorting, so he instead gives an example of ordered graph isomorphism. I do not understand why the author would make such an assumption; if the reader is assumed to already know about many applications of graph traversal, then why did the author spend 42 pages explaining what graph traversal is?

I believe one possible reason why the author does not discuss such "simpler" graph algorithms is that the LEDA library already has functions that implement algorithms like Dijkstra's, Bellman-Ford, MST, and max flow. However, the author does not spend time even defining what these problems are and only mentions the existence of these functions in the appendix.

Other things I did not like about the book:

- Much of the material seems to be simply cut-and-paste from one topic to the next. Case in point: the chunk of text saying "The problem of [problem] belongs to the class of NP-complete problems ... size of the graph" is pasted verbatim into at least four sections. Other lengthy passages are similarly pasted.

- The author's writing style makes reading the book more of a chore than it needs to be. My philosophy is that simple ideas should be explained simply, and I posit that this philosophy should be applicable to a depth-first traversal of a graph. However, the author is a bit formal in his explanation of DFS (among other topics), saying that "a simple procedure for a depth-first traversal of a graph consists of performing a preorder traversal upon each of the depth-first trees in the depth-first spanning forest of the graph" (p. 261). Compare this definition to the more fluid and intuitive definitions given by CLRS (2001) on page 540 and by Sedgewick's (Graph) Algorithms in C++ (2002) on page 87.

- As a minor point, the author uses the term "arc" whereas in the literature the more common term is "edge". I suppose this is not a big deal, but then the author defines a graph as having a vertex set V and an arc set E. Furthermore, in the LEDA appendix where the author is discussing the graph API that has word "edge" in the function calls (e.g. number_of_edges()), the author continues to use the term "arc".

- I am not sure if the C++ implementions using LEDA provided by the author really are helpful enough to outweigh their terseness and difficulty for reading. A better approach might have been CLRS-style pseudocode to explain the implementations. However, this book is really more of a LEDA applications guide, and I believe many people will find the code examples to be very helpful.

Now, here are the good points of this book that raise my rating from 3 stars to 4:

+ Chapter 2 is very, very nice. It uses a recurring example problem of tree edit-distance throughout four sections on backtracking, branch-and-bound, divide-and-conquer, and dynamic programming, thereby allowing the user to see how these different algorithmic approaches differ for a fixed problem. The discussion on tree edit-distance itself was new to me and very interesting.

+ The author makes nice use of examples throughout the book. Almost every theorem and definition is accompanied by an illustrated example.

+ The references are very thorough (at least for the time that the book was published), and the bibliographic section in each chapter, while short, frame the related work references very well.

+ The author consistently uses backtracking throughout the subgraph algorithm implementations, so it was good to hammer that down for the reader. However, it would have been nice to see the author discuss different implementations using dynamic programming (to attain some pseudo-polynomial time algorithm perhaps), approximation algorithms, or stochastic search (e.g. genetic algorithms).

In summary, this is a good book, but only if you are interested in the subgraph problems that the author covers.

3.0 out of 5 stars literate programming killed the book, March 29, 2010

By 

Chenna Reddy Cotla - See all my reviews

This review is from: Algorithms on Trees and Graphs (Hardcover)

Good on describing graph theory algorithms but is rendered bad due to that literate programming ... Simple algorithmic notation would have made the book much better...