 |
|
|
ALGORITHMIC GRAPH THEORY AND PERFECT GRAPHS, 57
| |
| | |
|
|
Second Edition
To order this title, and for more information, click here
Second Edition
By
Martin Golumbic, University of Haifa, Isreal.
Preface & Foreword
The publication of this new edition of Algorithmic Graph Theory and
Perfect Graphs marks twenty three years since its first appearance. My
original motivation for writing the book was to collect and unify the topic
to act as a spring board for researchers, and especially graduate students,
to pursue new directions of investigation. The ensuing years have been an
amazingly fruitful period of research in this area. To my great
satisfaction, the number of relevant journal articles in the literature has
grown tenfold. I can hardly express my admiration to all these authors for
creating a success story for algorithmic graph theory far beyond my own
imagination.
The world of perfect graphs has grown to include over 200 special graph
classes. The Venn diagrams that I used to show some of the inclusions
between classes in the First Generation, for example Figure 9.9 (on page
212), have yielded to Hasse diagrams for the Second Generation, like the one from Golumbic and Trenk [2003] reprinted in Figure 13.3 at the end of this edition.
Perhaps the most important new development in the theory of perfect graphs
is the recent proof of the Strong Perfect Graph Conjecture by Chudnovsky,
Robertson, Seymour and Thomas, announced in May 2002. News of this was
immediately passed on to Claude Berge, who sadly passed away on June 30,
2002.
On the algorithmic side, many of the problems which were open in 1980 have
been subsequently been settled, and algorithms on new classes of perfect
graphs have been studied. For example, tolerance graphs generalize both
interval graphs and permutation graphs, and coloring tolerance graphs in
polynomial time is important in solving scheduling problems where a measure
of flexibility or tolerance is allowed for sharing or relinquishing
resources when total exclusivity prevents a solution.
At the end of this new edition, I have added a short chapter called
Epilogue 2003 in which I survey a few of my favorite results and research
directions from the Second Generation. Its intention is to whet the appetite.
|
|
| |
| | |
|
|
| |
Home | Elsevier Websites | Privacy Policy | Terms and Conditions | Feedback | Site Map | A Reed Elsevier Company