Graph Theory, Computational Intelligence and Thought

Graph Theory, Computational Intelligence and Thought

Essays Dedicated to Martin Charles Golumbic on the Occasion of His 60th Birthday
Marina Lipshteyn, Vadim E. Levit, Ross M. McConnell (Eds.)

Martin Charles Golumbic has been making seminal contributions to algorithmic graph theory and artificial intelligence throughout his career. He is universally admired as a long-standing pillar of the discipline of computer science. He has contributed to the development of fundamental research in artificial intelligence in the area of complexity and spatial-temporal reasoning as well as in the area of compiler optimization. Golumbic's work in graph theory led to the study of new perfect graph families such as tolerance graphs, which generalize the classical graph notions of interval graph and comparability graph. He is credited with introducing the systematic study of algorithmic aspects in intersection graph theory, and initiated research on new structured families of graphs including the edge intersection graphs of paths in trees (EPT) and trivially perfect graphs.

Contents
Landmarks in Algorithmic Graph Theory: A Personal Retrospective - Martin Charles Golumbic - Pages 1-14
A Higher-Order Graph Calculus for Autonomic Computing - Oana Andrei, Hélène Kirchner - Pages 15-26
Algorithms on Subtree Filament Graphs - Fanica Gavril - Pages 27-35
A Note on the Recognition of Nested Graphs - Mark Korenblit, Vadim E. Levit - Pages 36-40
Asynchronous Congestion Games - Michal Penn, Maria Polukarov, Moshe Tennenholtz - Pages 41-53
Combinatorial Problems for Horn Clauses - Marina Langlois, Dhruv Mubayi, Robert H. Sloan, György Turán - Pages 54-65
Covering a Tree by a Forest - Fanica Gavril, Alon Itai - Pages 66-76
Dominating Induced Matchings - Domingos M. Cardoso, Vadim V. Lozin - Pages 77-86
HyperConsistency Width for Constraint Satisfaction: Algorithms and Complexity Results - Georg Gottlob, Gianluigi Greco, Bruno Marnette Pages - 87-99
Local Search Heuristics for the Multidimensional Assignment Problem - G. Gutin, D. Karapetyan - Pages 100-115
On Distance-3 Matchings and Induced Matchings - Andreas Brandstädt, Raffaele Mosca - Pages 116-126
On Duality between Local Maximum Stable Sets of a Graph and Its Line-Graph - Vadim E. Levit, Eugen Mandrescu - Pages 127-133
On Path Partitions and Colourings in Digraphs - Irith Ben-Arroyo Hartman - Pages 134-143
On Related Edges in Well-Covered Graphs without Cycles of Length 4 and 6 - Vadim E. Levit, David Tankus - Pages 144-147
On the Cubicity of AT-Free Graphs and Circular-Arc Graphs - L. Sunil Chandran, Mathew C. Francis, Naveen Sivadasan - Pages 148-157
O(m logn) Split Decomposition of Strongly Connected Graphs - Benson L. Joeris, Scott Lundberg, Ross M. McConnell - Pages 158-171
Path-Bicolorable Graphs - Andreas Brandstädt, Martin C. Golumbic, Van Bang Le, Marina Lipshteyn - Pages 172-182
Path Partitions, Cycle Covers and Integer Decomposition - András Sebő - Pages 183-199
Properly Coloured Cycles and Paths: Results and Open Problems - Gregory Gutin, Eun Jung Kim - Pages 200-208
Recognition of Antimatroidal Point Sets - Yulia Kempner, Vadim E. Levit - Pages 209-216
Tree Projections: Game Characterization and Computational Aspects - Georg Gottlob, Gianluigi Greco, Zoltán Miklós, Francesco Scarcello, Thomas Schwentick - Pages 217-226

Springer, Lecture Notes in Computer Science (LNCS) - Volume 5420, Paperback, english, 244 pages