Ebook: Graph Theory, Computational Intelligence and Thought: Essays Dedicated to Martin Charles Golumbic on the Occasion of His 60th Birthday

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.

Golumbic is currently the founder and director of the Caesarea Edmond Benjamin de Rothschild Institute for Interdisciplinary Applications of Computer Science at the University of Haifa. He also served as chairman of the Israeli Association of Artificial Intelligence (1998-2004), and founded and chaired numerous international symposia in discrete mathematics and in the foundations of artificial intelligence.

This Festschrift volume, published in honor of Martin Charles Golumbic on the occasion of his 60th birthday, contains 20 papers, written by graduate students, research collaborators, and computer science colleagues, who gathered at a conference on subjects related to Martin Golumbic's manifold contributions in the field of algorithmic graph theory and artificial intelligence, held in Jerusalem, Tiberias and Haifa, Israel in September 2008.

---

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.

Golumbic is currently the founder and director of the Caesarea Edmond Benjamin de Rothschild Institute for Interdisciplinary Applications of Computer Science at the University of Haifa. He also served as chairman of the Israeli Association of Artificial Intelligence (1998-2004), and founded and chaired numerous international symposia in discrete mathematics and in the foundations of artificial intelligence.

This Festschrift volume, published in honor of Martin Charles Golumbic on the occasion of his 60th birthday, contains 20 papers, written by graduate students, research collaborators, and computer science colleagues, who gathered at a conference on subjects related to Martin Golumbic's manifold contributions in the field of algorithmic graph theory and artificial intelligence, held in Jerusalem, Tiberias and Haifa, Israel in September 2008.

---

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.

Golumbic is currently the founder and director of the Caesarea Edmond Benjamin de Rothschild Institute for Interdisciplinary Applications of Computer Science at the University of Haifa. He also served as chairman of the Israeli Association of Artificial Intelligence (1998-2004), and founded and chaired numerous international symposia in discrete mathematics and in the foundations of artificial intelligence.

This Festschrift volume, published in honor of Martin Charles Golumbic on the occasion of his 60th birthday, contains 20 papers, written by graduate students, research collaborators, and computer science colleagues, who gathered at a conference on subjects related to Martin Golumbic's manifold contributions in the field of algorithmic graph theory and artificial intelligence, held in Jerusalem, Tiberias and Haifa, Israel in September 2008.

Content:
Front Matter....Pages -
Landmarks in Algorithmic Graph Theory: A Personal Retrospective....Pages 1-14
A Higher-Order Graph Calculus for Autonomic Computing....Pages 15-26
Algorithms on Subtree Filament Graphs....Pages 27-35
A Note on the Recognition of Nested Graphs....Pages 36-40
Asynchronous Congestion Games....Pages 41-53
Combinatorial Problems for Horn Clauses ....Pages 54-65
Covering a Tree by a Forest....Pages 66-76
Dominating Induced Matchings....Pages 77-86
HyperConsistency Width for Constraint Satisfaction: Algorithms and Complexity Results....Pages 87-99
Local Search Heuristics for the Multidimensional Assignment Problem....Pages 100-115
On Distance-3 Matchings and Induced Matchings....Pages 116-126
On Duality between Local Maximum Stable Sets of a Graph and Its Line-Graph....Pages 127-133
On Path Partitions and Colourings in Digraphs....Pages 134-143
On Related Edges in Well-Covered Graphs without Cycles of Length 4 and 6....Pages 144-147
On the Cubicity of AT-Free Graphs and Circular-Arc Graphs....Pages 148-157
Path-Bicolorable Graphs....Pages 158-171
Path Partitions, Cycle Covers and Integer Decomposition....Pages 172-182
Properly Coloured Cycles and Paths: Results and Open Problems....Pages 183-199
Recognition of Antimatroidal Point Sets....Pages 200-208
Back Matter....Pages 209-216
Tree Projections: Game Characterization and Computational Aspects....Pages -
....Pages 217-226