You are here

Algorithmic Aspects of Graph Connectivity

Hiroshi Nagamochi and Toshihide Ibaraki
Cambridge University Press
Publication Date: 
Number of Pages: 
Encyclopedia of Mathematics and its Applications 123
[Reviewed by
Celina Miraglia Herrera de Figueiredo
, on

Graphs model how objects are connected. Because of its many applications, the subject of Graph Theory is present in many undergraduate and graduate courses of discrete mathematics, computer science, and operations research. Recent research has explored the algorithmic aspects of the subject. There are, of course, many excelent Graph Theory textbooks; the present book answers the need of a unified discussion of both graph connectivity and efficient algorithms.

The book is a research monograph on the concept of maximum adjacency ordering and the computational complexity of algorithms. It discusses many variations on the definition of graph connectivity: edge-connectivity, vertex-connectivity, flows, and cuts. The book covers both basic definitions and advanced topics, and so may be used as a textbook in graduate courses of discrete mathematics or operations research. Additionally, the book discusses new algorithms and covers the recent publications on the subject, many of them by the two authors, which makes the book a useful reference for specialists working in discrete mathematics and its applications.

The book's goal is achieved through a rich discussion that includes approximation algorithms, randomized algorithms, dynamic algorithms, experimental results, aspects of algorithm analysis (complexity and efficiency) and aspects of problem analysis (optimality of solutions and enumeration of possible solutions).

Celina Miraglia Herrera de Figueiredo is professor at the Systems Engineering and Computer Science Program of COPPE at the Federal University of Rio de Janeiro. Her main interests are analysis of algorithms and problem complexity, graph theory, and perfect graphs.