1st Edition

Handbook of Graph Theory, Combinatorial Optimization, and Algorithms

    1244 Pages 345 B/W Illustrations
    by Chapman & Hall

    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.

    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

    Biography

    Editor-in-Chief
    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.

    Editors
    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.

    "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.