Algorithmic graph theory and perfect graphs / Martin Charles Golumbic

Bibliogr. dispersée. Notes bibliogr. Index

M. C. Golumbic’s book has now become the classic introduction to graph classes characterised by intersection models or elimination orderings. The first edition [Algorithmic graph theory and perfect graphs (Computer Science and Applied Mathematics; New York etc.: Academic Press. A Subsidiary of Harcourt Brace Jovanovich, Publishers. XX) (1980; Zbl 0541.05054)] consists of 12 chapters entitled graph theoretic foundations, the design of efficient algorithms, perfect graphs, triangulated graphs (also known as chordal graphs), comparability graphs, split graphs, permutation graphs, interval graphs, superperfect graphs, threshold graphs, not so perfect graphs (circle graphs), perfect Gaussian elimination, and an appendix. The second edition presents this material in exactly the same way. Additionally it contains a foreword 2004, a list of corrections and an epilogue 2004. The latter mentions the strong perfect graph theorem and classes of graphs that attained attention after 1980, among them strongly and weakly chordal graphs, cographs, asteroidal triple-free graphs, tolerance graphs, and circular-arc graphs as well as algorithms processing graphs in these classes. (Zentralblatt)