Handbook of Graph Theory, Combinatorial Optimization, and Algorithms: 1st Edition (Hardback) book cover

Handbook of Graph Theory, Combinatorial Optimization, and Algorithms

1st Edition

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

Chapman and Hall/CRC

1,226 pages | 345 B/W Illus.

Purchasing Options:$ = USD
Hardback: 9781584885955
pub: 2015-12-14
SAVE ~$33.00
eBook (VitalSource) : 9780429150234
pub: 2016-01-05
from $28.98

FREE Standard Shipping!


The fusion between graph theory and combinatorial optimization has led to theoretically profound and practically useful algorithms, yet there is no book that currently covers both areas together. Handbook of Graph Theory, Combinatorial Optimization, and Algorithms is the first to present a unified, comprehensive treatment of both graph theory and combinatorial optimization.

Divided into 11 cohesive sections, the handbook’s 44 chapters focus on graph theory, combinatorial optimization, and algorithmic issues. The book provides readers with the algorithmic and theoretical foundations to:

  • Understand phenomena as shaped by their graph structures
  • Develop needed algorithmic and optimization tools for the study of graph structures
  • Design and plan graph structures that lead to certain desirable behavior

With contributions from more than 40 worldwide experts, this handbook equips readers with the necessary techniques and tools to solve problems in a variety of applications. Readers gain exposure to the theoretical and algorithmic foundations of a wide range of topics in graph theory and combinatorial optimization, enabling them to identify (and hence solve) problems encountered in diverse disciplines, such as electrical, communication, computer, social, transportation, biological, and other networks.


"To sum up,this book gives a lucid, deep,and panoramic view of ofgraphtheory, both broadly conceived and concentrating on its algorithmic and combinatorial optimization aspects. It will be of immense use to anyone with an interest in the area, researcher, teacher, or student, as a reference work or as a resource for self-study. It is a weighty but attractive volume, rich in content and richly illustrated. I highly recommended it!"

Frederic Green, Department of Mathematics and Computer Science Clark University Worcester.

Table of Contents

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


Subramanian Arumugam and Karam Ebadi

Connectivity Algorithms

Krishnaiyan "KT" Thulasiraman

Graph Connectivity Augmentation

András Frank and Tibor Jordán


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


Graph and Hypergraph Partitioning

Sachin B. Patkar and H. Narayanan



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

About the Editors


Krishnaiyan "KT" Thulasiraman is a professor and Hitachi Chair in Computer Science at the University of Oklahoma and a professor emeritus in electrical and computer engineering at Concordia University in Montreal. He is a fellow of the IEEE, AAAS, and the European Academy of Sciences. Dr. Thulasiraman has received several honors, including the Distinguished Alumnus Award of the Indian Institute of Technology Madras, IEEE Circuits and Systems Society Charles Desoer Technical Achievement Award, and IEEE Circuits and Systems Society Golden Jubilee Medal. He is the coauthor of two graduate-level textbooks on graphs, electrical networks, and algorithms. His research interests include graph theory, combinatorial optimization, and related algorithmic issues with a specific focus on applications in electrical and computer engineering and network science.


Subramanian Arumugam is a senior professor and director of the National Centre for Advanced Research in Discrete Mathematics at Kalasalingam University. He is also a visiting professor at Liverpool Hope University and an adjunct professor at Ball State University. Dr. Arumugam is the founding editor-in-chief of AKCE International Journal of Graphs and Combinatorics and author of 32 books and 195 journal papers. His current research interests include graph theory and its applications.

Andreas Brandstädt retired as a professor in computer science from the University of Rostock after 20 years. Dr. Brandstädt has published extensively in various international journals and conference proceedings. He is also the author of a textbook and coauthor of a widely cited monograph. His research interests include stochastics, complexity theory, formal languages, graph algorithms, graph theory, combinatorial optimization, and related algorithmic issues with a specific focus on efficient algorithms based on graph structure and graph classes with tree structure.

Takao Nishizeki is a professor emeritus at Tohoku University. He is a fellow of the ACM, IEEE, IEICE of Japan, Information Processing Society of Japan, and Bangladesh Academy of Sciences. Dr. Nishizeki has received several honors, including the Science and Technology Prize of the Japanese Ministry of Education, IEICE Achievement Award, ICF Best Research Award, Funai Information Science Promotion Award, TELECOM Technology Award, and many awards for best paper. His research interests include algorithms for planar graphs, edge coloring, network flows, VLSI routing, graph drawing, and cryptology.

About the Series

Chapman & Hall/CRC Computer and Information Science Series

Learn more…

Subject Categories

BISAC Subject Codes/Headings:
COMPUTERS / Operating Systems / General
COMPUTERS / Programming / Algorithms
MATHEMATICS / Combinatorics