Topics in Algorithmic Graph Theory

Description

Algorithmic graph theory has been expanding at an extremely rapid rate since the middle of the twentieth century, in parallel with the growth of computer science and the accompanying utilization of computers, where efficient algorithms have been a prime goal. This book presents material on developments on graph algorithms and related concepts that will be of value to both mathematicians and computer scientists, at a level suitable for graduate students, researchers and instructors. The fifteen expository chapters, written by acknowledged international experts on their subjects, focus on the application of algorithms to solve particular problems. All chapters were carefully edited to enhance readability and standardize the chapter structure as well as the terminology and notation. The editors provide basic background material in graph theory, and a chapter written by the book's Academic Consultant, Martin Charles Golumbic (University of Haifa, Israel), provides background material on algorithms as connected with graph theory. Front matter Copyright Contents Foreword Preface Preliminaries 1. Graph theory 2. Connectivity 3. Optimization problems on graphs 4. Structured families of graphs 5. Directed graphs 1 Graph algorithms 1. Introduction 2. Graph search algorithms 3. Greedy graph colouring 4. The structured graph approach 5. Specialized classes of intersection graphs 2 Graph colouring variations 1. Introduction 2. Selective graph colouring 3. Online colouring 4. Mixed graph colouring 3 Total colouring 1. Introduction 2. Hilton's condition 3. Cubic graphs 4. Equitable total colourings 5. Vertex-elimination orders 6. Decomposition 7. Complexity separation 8. Concluding remarks and conjectures 4 Testing of graph properties 1. Introduction 2. The dense graph model 3. Testing graph properties in the dense graph model 4. Historical notes 5. The incidence-list model 6. Final comments 5 Cliques, colouring and satisfiability - from structure to algorithms 1. Introduction 2. Hereditary classes and graph problems 3. From structure... 4. ... to algorithms 5. Concluding remarks and open problems 6 Chordal graphs 1. Introduction 2. Minimal separators 3. Perfect elimination 4. Tree representations and clique-trees S. Superclasses of chordal graphs 6. Subclasses of chordal graphs 7. Applications of chordal graphs 8. Concluding remarks 7 Dually and strongly chordal graphs 1. Introduction 2. The hypergraph view of chordal graphs 3. Dually chordal graphs 4. Strongly chordal graphs 5. Chordal bipartite graphs 8 Leaf powers 1. Introduction 2. Basic properties of leaf powers 3. Recognition algorithms for leaf powers 4. Classification and forbidden subgraphs 5. Simplicial powers and phylogenetic powers 6. Concluding remarks 9 Split graphs 1. Introduction 2. Related classes of perfect graphs 3. Degree sequence characterizations 4. Ferrers diagrams and majorizalion 5. Three-part partitions, NG-graphs and pseudo-split graphs 6. Bijections, counting and the compilation theorem 7. Tyshkevich decomposition 10 Strong cliques and stable sets 1. Introduction 2. Connections with perfect graphs 3. CIS, general partition and localizable graphs 4. Algorithmic and complexity issues 5. Vertex-transitive graphs 6. Related concepts and applications 7. Open problems 11 Restricted matchings 1. Introduction 2. Basic results 3. Equality of the matching numbers 4. Hardness results 5. Bounds 6. Tractable cases 7. Approximation algorithms 12 Covering geometric domains 1. Introduction 2. Preliminaries 3. The perfect graph approach 4. Polygon covering problems 5. Covering discrete sets 13 Graph homomorphisms 1. Introduction 2. Homomorphisms of graphs 3. Homomorphisms of digraphs 4. Injective and surjective homomorphisms 5. Retracts and cores 6. Median graphs and absolute retracts 7. List homomorphisms 8. Computational problems 9. The basic homomorphism problem HOM(H) 10. Duality 11. Polymorphisms 12. The list homomorphism problems LHOM(H) 13. The retraction problems RET(H) 14. The surjective versions SHOM(H), COMP(H) 15. Conclusions and generalizations 14 Sparsity and model theory 1. Introduction 2. There is depth in shallowness 3. Orientation and decomposition 4. Born to be wide 5. Everything gets easier when you follow orders 6. When dependence leads to stability 7. Conclusion: can dense graphs be sparse? 15 Extremal vertex-sets 1. Introduction 2. Enumeration algorithms 3. Lower bounds 4. Measure & conquer 5. Monotone local search 6. Applications to exponential-time algorithms 7. Conclusion Index