Handbook of Graph Theory, Combinatorial Optimization, and Algorithms

Krishnaiyan “KT” Thulasiraman, Subramanian Arumugam, Andreas Brandstädt, Takao Nishizeki, editors

Publisher:

Chapman & Hall/CRC

Publication Date:

2016

Number of Pages:

1226

Format:

Hardcover

Series:

Chapman & Hall/CRC Computer and Information Science Series

Price:

119.96

ISBN:

9781584885955

Category:

Handbook

BLL Rating:

BLL

The Basic Library List Committee suggests that undergraduate mathematics libraries consider this book for acquisition.

MAA Review
Table of Contents

[Reviewed by

Miklós Bóna

, on

10/7/2016

]

The subject of graph theory is so vast that it has generated a huge number of comprehensive volumes. Therefore, even in the case of a book of more than 1100 pages with a very general title, the reviewer must inform his readers just exactly what it is that the book does.

The answer in this case is that a title like “Handbook of Graph Algorithms” would have been much better. Everything in the book is about graphs, so it is unfortunate to suggest that the book is about graph theory, and other things. The book studies a great many aspects of graphs, but algorithms are always front and center. There is, of course, nothing wrong with that perspective; it would simply have been more informative to state it in the title. Most of the important subfields of graph theory are at least touched upon here, but the angle is always algorithmic, instead of, say, structural or enumerative.

There are several ways in which the editor of a huge volume like this can proceed. In this book, we see a two-layered structure, with nine parts (called, a bit oddly, “Sections”), and 44 chapters. It is probably much harder for the editor to keep so many different chapter authors in line than to do the same if he had, say, 11 authors responsible for a hundred pages each. However, as the book’s primary use will be as a reference volume anyway, it iis probably not a big problem if two chapters 500 pages away repeat the same facts or refer to the same articles.

The entire book is written in a reader-friendly style, with facts broken down to many smaller theorems and lemmas, which enables the authors to show proofs that are not overly long or technical. The book is likely to become a go-to source for those who need information on algorithms on graphs.

Miklós Bóna is Professor of Mathematics at the University of Florida.

Basic Concepts and Algorithms
Basic Concepts in Graph Theory and Algorithms
Subramanian Arumugam and Krishnaiyan "KT" Thulasiraman
Basic Graph Algorithms
Krishnaiyan "KT" Thulasiraman
Depth-First Search and Applications
Krishnaiyan "KT" Thulasiraman

Flows in Networks
Maximum Flow Problem
F. Zeynep Sargut, Ravindra K. Ahuja, James B. Orlin, and Thomas L. Magnanti
Minimum Cost Flow Problem
Balachandran Vaidyanathan, Ravindra K. Ahuja, James B. Orlin, and Thomas L. Magnanti
Multi-Commodity Flows
Balachandran Vaidyanathan, Ravindra K. Ahuja, James B. Orlin, and Thomas L. Magnanti

Algebraic Graph Theory
Graphs and Vector Spaces
Krishnaiyan "KT" Thulasiraman and M.N.S. Swamy
Incidence, Cut, and Circuit Matrices of a Graph
Krishnaiyan "KT" Thulasiraman and M.N.S. Swamy
Adjacency Matrix and Signal Flow Graphs
Krishnaiyan "KT" Thulasiraman and M.N.S. Swamy
Adjacency Spectrum and the Laplacian Spectrum of a Graph
R. Balakrishnan
Resistance Networks, Random Walks, and Network Theorems
Krishnaiyan "KT" Thulasiraman and Mamta Yadav

Structural Graph Theory
Connectivity
Subramanian Arumugam and Karam Ebadi
Connectivity Algorithms
Krishnaiyan "KT" Thulasiraman
Graph Connectivity Augmentation
András Frank and Tibor Jordán
Matchings
Michael D. Plummer
Matching Algorithms
Krishnaiyan "KT" Thulasiraman
Stable Marriage Problem
Shuichi Miyazaki
Domination in Graphs
Subramanian Arumugam and M. Sundarakannan
Graph Colorings
Subramanian Arumugam and K. Raja Chandrasekar

Planar Graphs
Planarity and Duality
Krishnaiyan "KT" Thulasiraman and M.N.S. Swamy
Edge Addition Planarity Testing Algorithm
John M. Boyer
Planarity Testing Based on PC-Trees
Wen-Lian Hsu
Graph Drawing
Md. Saidur Rahman and Takao Nishizeki

Interconnection Networks
Introduction to Interconnection Networks
S.A. Choudum, Lavanya Sivakumar, and V. Sunitha
Cayley Graphs
S. Lakshmivarahan, Lavanya Sivakumar, and S.K. Dhall
Graph Embedding and Interconnection Networks
S.A. Choudum, Lavanya Sivakumar, and V. Sunitha

Special Graphs
Program Graphs
Krishnaiyan "KT" Thulasiraman
Perfect Graphs
Chính T. Hoàng and R. Sritharan
Tree-Structured Graphs
Andreas Brandstädt and Feodor F. Dragan

Partitioning
Graph and Hypergraph Partitioning
Sachin B. Patkar and H. Narayanan

Matroids
Matroids
H. Narayanan and Sachin B. Patkar
Hybrid Analysis and Combinatorial Optimization
H. Narayanan

Probabilistic Methods, Random Graph Models, and Randomized Algorithms
Probabilistic Arguments in Combinatorics
C.R. Subramanian
Random Models and Analyses for Chemical Graphs
Daniel Pascua, Tina M. Kouri, and Dinesh P. Mehta
Randomized Graph Algorithms: Techniques and Analysis
Surender Baswana and Sandeep Sen

Coping with NP-Completeness
General Techniques for Combinatorial Approximation
Sartaj Sahni
ε-Approximation Schemes for the Constrained Shortest Path Problem
Krishnaiyan "KT" Thulasiraman
Constrained Shortest Path Problem: Lagrangian Relaxation-Based Algorithmic Approaches
Ying Xiao and Krishnaiyan "KT" Thulasiraman
Algorithms for Finding Disjoint Paths with QoS Constraints
Alex Sprintson and Ariel Orda
Set-Cover Approximation
Neal E. Young
Approximation Schemes for Fractional Multicommodity Flow Problems
George Karakostas
Approximation Algorithms for Connectivity Problems
Ramakrishna Thurimella
Rectilinear Steiner Minimum Trees
Tao Huang and Evangeline F.Y. Young
Fixed-Parameter Algorithms and Complexity
Venkatesh Raman and Saket Saurabh