Algorithms on Trees and Graphs

Graph algorithms is a wellestablished subject in mathematics and computerscience. Beyond classical application fields like approximation combinatorialoptimizati... » 

Graph algorithms is a wellestablished subject in mathematics and computerscience. Beyond classical application fields like approximation combinatorialoptimization graphics and operations research graph algorithms have recentlyattracted increased attention from computational molecular biology andcomputational chemistry. Centered around the fundamental issue of graphisomorphism this text goes beyond classical graph problems of shortest pathsspanning trees flows in networks and matchings in bipartite graphs. Advancedalgorithmic results and techniques of practical relevance are presented in acoherent and consolidated way. This book introduces graph algorithms on anintuitive basis followed by a detailed exposition in a literate programmingstyle with correctness proofs as well as worstcase analyses. Furthermorefull C implementations of all algorithms presented are given using the LEDAlibrary of efficient data structures and algorithms. Numerous illustrationsexamples and exercises and a comprehensive bibliography support students andprofessionals in using the book as a text and source of reference TOCPreface.Part I. Introduction 1. Introduction. 2. Algorithmic Techniques. Part II.Algorithms on Trees 3. Tree Traversal. 4. Tree Isomorphism. Part III.Algorithms on Graphs 5. Graph Traversal. 6. Clique Independent Set andVertex Cover. 7. Graph Isomorphism Appendices A. An Overview of Leda. B.Interactive Demonstration of Graph Algorithms. C. Program Modules. References. Index. «