Skip to main content
SpringerLink
Log in

Graph Theory, Computational Intelligence and Thought

Essays Dedicated to Martin Charles Golumbic on the Occasion of His 60th Birthday

  • Book
  • © 2009

Overview

Editors:
  1. Marina Lipshteyn

    1. The Caesarea Rothschild Institute, Mount Carmel, University of Haifa, Haifa, Israel

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. Vadim E. Levit

    1. Department of Computer Science and Mathematics, Ariel University Center of Samaria, Ariel, Israel

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  3. Ross M. McConnell

    1. Department of Computer Science, Colorado State University, Fort Collins, USA

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

Part of the book series: Lecture Notes in Computer Science (LNCS, volume 5420)

Part of the book sub series: Theoretical Computer Science and General Issues (LNTCS)

This is a preview of subscription content, log in via an institution to check access.

Access this book

Log in via an institution
eBook USD 39.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Other ways to access

Licence this eBook for your library

Institutional subscriptions

Table of contents (21 chapters)

  1. Front Matter

    Download chapter PDF

  2. Landmarks in Algorithmic Graph Theory: A Personal Retrospective

    • Martin Charles Golumbic
    Pages 1-14

  3. A Higher-Order Graph Calculus for Autonomic Computing

    • Oana Andrei, Hélène Kirchner
    Pages 15-26

  4. Algorithms on Subtree Filament Graphs

    • Fanica Gavril
    Pages 27-35

  5. A Note on the Recognition of Nested Graphs

    • Mark Korenblit, Vadim E. Levit
    Pages 36-40

  6. Asynchronous Congestion Games

    • Michal Penn, Maria Polukarov, Moshe Tennenholtz
    Pages 41-53

  7. Combinatorial Problems for Horn Clauses

    • Marina Langlois, Dhruv Mubayi, Robert H. Sloan, György Turán
    Pages 54-65

  8. Covering a Tree by a Forest

    • Fanica Gavril, Alon Itai
    Pages 66-76

  9. Dominating Induced Matchings

    • Domingos M. Cardoso, Vadim V. Lozin
    Pages 77-86

  10. HyperConsistency Width for Constraint Satisfaction: Algorithms and Complexity Results

    • Georg Gottlob, Gianluigi Greco, Bruno Marnette
    Pages 87-99

  11. Local Search Heuristics for the Multidimensional Assignment Problem

    • G. Gutin, D. Karapetyan
    Pages 100-115

  12. On Distance-3 Matchings and Induced Matchings

    • Andreas Brandstädt, Raffaele Mosca
    Pages 116-126

  13. On Duality between Local Maximum Stable Sets of a Graph and Its Line-Graph

    • Vadim E. Levit, Eugen Mandrescu
    Pages 127-133

  14. On Path Partitions and Colourings in Digraphs

    • Irith Ben-Arroyo Hartman
    Pages 134-143

  15. On Related Edges in Well-Covered Graphs without Cycles of Length 4 and 6

    • Vadim E. Levit, David Tankus
    Pages 144-147

  16. On the Cubicity of AT-Free Graphs and Circular-Arc Graphs

    • L. Sunil Chandran, Mathew C. Francis, Naveen Sivadasan
    Pages 148-157

  17. O(m logn) Split Decomposition of Strongly Connected Graphs

    • Benson L. Joeris, Scott Lundberg, Ross M. McConnell
    Pages 158-171

  18. Path-Bicolorable Graphs

    • Andreas Brandstädt, Martin C. Golumbic, Van Bang Le, Marina Lipshteyn
    Pages 172-182

  19. Path Partitions, Cycle Covers and Integer Decomposition

    • András Sebő
    Pages 183-199

  20. Properly Coloured Cycles and Paths: Results and Open Problems

    • Gregory Gutin, Eun Jung Kim
    Pages 200-208
Back to top

Keywords

About this book

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.

Reviews

From the reviews: “In 2008, a weeklong conference was organized to celebrate Golumbic’s 60th birthday. This volume is a collection of the conference proceedings … . It contains 20 papers, in addition to Golumbic’s conference lecture. … papers are accessible even to readers who only have a rudimentary understanding of Golumbic’s work. … Three groups of people would benefit from reading this volume: researchers in Golumbic’s circle, researchers … who are looking for a new frontier to, and graduate students in pursuit of a research topic.” (San Skulrattanakulchai, ACM Computing Reviews, March, 2009)

Editors and Affiliations

  • The Caesarea Rothschild Institute, Mount Carmel, University of Haifa, Haifa, Israel

    Marina Lipshteyn

  • Department of Computer Science and Mathematics, Ariel University Center of Samaria, Ariel, Israel

    Vadim E. Levit

  • Department of Computer Science, Colorado State University, Fort Collins, USA

    Ross M. McConnell

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation