Your query: an = (919.05001)
Answers 1-1 (of 1)
[New query form]
919.05001
Brandstaedt, Andreas; Le, Van Bang; Spinrad, Jeremy P.
Graph classes: a survey. (English)
[B] SIAM Monographs on Discrete Mathematics and Applications. Philadelphia, PA: SIAM. xi, 304 p. \$ 68.00 (1999). [ISBN 0-89871-432-X/pbk]
In the past years, hundreds of graph classes have been invented and studied, both with respect to their structural properties as to their algorithmic complexity. In this book, many important graph classes are reviewed and discussed, with respect to these properties. The book discusses over 200 graph classes, their relations (which graph class is properly contained in which graph class), and key theorems. Both structural results are given (e.g., equivalent characterization of a graph property) and algorithmic behaviour is discussed, e.g., what is the complexity of deciding if a given graph belongs to the class, or polynomial time solvability or NP-completeness of important problems restricted to the class.\par
The material is organized with respect to types of properties: there are fourteen chapters on subjects like perfect graphs (and generalizations and related concepts), forbidden subgraphs, distance properties, and more. Theorems are given without a proof, but with a reference to the literature where the result can be found. There are 1098 references. In this way, the book provides an encyclopedic overview of very many results that are important for researchers on graph classes, and is very useful as a work of reference for those working in the field.
[ H.Bodlaender (Utrecht) ]
- MSC 1991:
-
*05-02 Research monographs (combinatorics)
05Cxx Graph theory
05C75 Structural characterization of types of graphs
05C85 Graphic algorithms
Keywords: algorithmic complexity; graph class; NP-completeness; perfect graphs; forbidden subgraphs; distance
Cited in Zbl. reviews...
On line ordering services 
[New query form]Answers 1-1 (of 1)
Zentralblatt MATH,
Copyright (c) 2000 European Mathematical Society, FIZ Karlsruhe & Springer-Verlag.