Algorithmic graph theory and perfect graphs / Martin Charles Golumbic

Auteur: Golumbic, Martin Charles (1948-) - AuteurType de document: MonographieCollection: Annals of discrete mathematics ; 57Langue: anglaisPays: Pays BasÉditeur: Amsterdam : Elsevier, 2004Edition: 2nd editionDescription: 1 vol. (XXVI-314 p.) : fig. ; 24 cm ISBN: 9780444515308 ; rel. Résumé: 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).Bibliographie: Bibliogr. dispersée. Notes bibliogr. Index. Sujets MSC: 05C62 Combinatorics -- Graph theory -- Graph representations (geometric and intersection representations, etc.)
05C15 Combinatorics -- Graph theory -- Coloring of graphs and hypergraphs
05C17 Combinatorics -- Graph theory -- Perfect graphs
05C85 Combinatorics -- Graph theory -- Graph algorithms
68Q25 Computer science -- Theory of computing -- Analysis of algorithms and problem complexity
68R10 Computer science -- Discrete mathematics in relation to computer science -- Graph theory (including graph drawing)
En-ligne: Zentralblatt | MathSciNet
Location Call Number Status Date Due
Salle R 07613-01 / 05 GOL (Browse Shelf) Available

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)

There are no comments for this item.

Log in to your account to post a comment.
Languages: English | Français | |