Gabriel Valiente - Algorithms on Trees and Graphs: With Python Code

More information about this series at http://www.springer.com/series/3191

This Springer imprint is published by the registered company Springer Nature Switzerland AG

The registered company address is: Gewerbestrasse 11, 6330 Cham, Switzerland

The first edition of this book has been extensively used for graduate teaching and research all over the world in the last two decades. We have listed hundreds of citing publications in Appendix C, including books, scientific articles in journals and conference proceedings, M.Sc. and Ph.D. theses, and even United States patents.

In this new edition, we have substituted detailed pseudocode for both the literate programming description and the implementation of the algorithms using the LEDA library of efficient data structures and algorithms. Although the pseudocode is detailed enough to allow for a straightforward implementation of the algorithms in any modern programming language, we have added a proof-of-concept implementation in Python of all the algorithms in Appendix A. This is, therefore, a thoroughly revised and extended edition.

Regarding new material, we have added an adjacency map representation of trees and graphs, and both maximum cardinality and maximum weight bipartite matching as an additional application of graph traversal techniques. Further, we have revised the end-of-chapter problems and exercises and have included solutions to all the problems in Appendix B.

It has been a pleasure for the author to work out editorial matters together with Sriram Srinivas and, especially, Wayne Wheeler of Springer Nature, whose standing support and encouragement have made this new edition possible.

Last, but not least, any minor errors found so far have been corrected in this second edition, the bibliographic notes and references have been updated, and the index has been substantially enhanced. Even though the author and the publisher have taken much care in the preparation of this book, they make no representation, express or implied, with regard to the accuracy of the information contained herein and cannot accept any legal responsibility or liability for incidental or consequential damages arising out of the use of the information, algorithms, or program code contained in this book.

Graph algorithms, a long-established subject in mathematics and computer science curricula, are also of much interest to disciplines such as computational molecular biology and computational chemistry. This book goes beyond the classical graph problems of shortest paths, spanning trees, flows in networks, and matchings in bipartite graphs, and addresses further algorithmic problems of practical application on trees and graphs. Much of the material presented on the book is only available in the specialized research literature.

The book is structured around the fundamental problem of isomorphism. Tree isomorphism is covered in much detail, together with the related problems of subtree isomorphism, maximum common subtree isomorphism, and tree comparison. Graph isomorphism is also covered in much detail, together with the related problems of subgraph isomorphism, maximal common subgraph isomorphism, and graph edit distance. A building block for solving some of these isomorphism problems are algorithms for finding maximal and maximum cliques.

Most intractable graph problems of practical application are not even approximable to within a constant bound, and several of the isomorphism problems addressed in this book are no exception. The book can thus be seen as a companion to recent texts on approximation algorithms [1, 16], but also as a complement to previous texts on combinatorial and graph algorithms [215, 17].

The book is conceived on the ground of first, introducing simple algorithms for these problems in order to develop some intuition before moving on to more complicated algorithms from the research literature and second, stimulating graduate research on tree and graph algorithms by providing together with the underlying theory, a solid basis for experimentation and further development.

Algorithms are presented on an intuitive basis, followed by a detailed exposition in a literate programming style. Correctness proofs are also given, together with a worst-case analysis of the algorithms. Further, full C++ implementation of all the algorithms using the LEDA library of efficient data structures and algorithms is given along the book. These implementations include result checking of implementation correctness using correctness certificates.

The choice of LEDA, which is becoming a de-facto standard for graduate courses on graph algorithms throughout the world is not casual, because it allows the student, lecturer, researcher, and practitioner to complement algorithmic graph theory with actual implementation and experimentation, building upon a thorough library of efficient implementations of modern data structures and fundamental algorithms.