Brandst?dt A., van Bang L., Spinrad J.P. Graph Classes: a Survey



Brandst?dt A., van Bang L., Spinrad J.P. Graph Classes: a Survey
31.01.2012 в 00:54 2.64 Мб djvu 7 раз
Society for Industrial and Applied Mathematics, 1999, -321 pp.

When dealing with special graph classes and algorithmic problems on them, a main source is the classical book of Golumbic, Algorithmic Graph Theory and Perfect Graphs. The book, however, appeared in 1980, and since that time many interesting new classes have been introduced. Therefore, it is probably useful to have a new survey that attempts to describe the world of special graph classes with an emphasis on the algorithmic point of view.
There are many reasons for the interest in this field of research. These come from discrete mathematics as well as theoretical arid practical computer science. discrete mathematics as well as theoretical arid practical computer science.
Graphs are a good model for describing "real-world" and computer-science situations such as
— interconnection and transport networks for information exchange;
— VLSI layouts;
— computational geometry;
— graph drawing;
— scheduling and partial-order problems;
— molecular biology (DNAmappings), phylogenetic trees;
— temporal reasoning;
— synchronizing parallel processes;
— sparse systems of linear equations;
— desirable properties of relational database schemes.
The last properties are closely related to hypergraph acyclicity, Helly and tree properties of hypergraphs, and graph chordality.
For many applications, the graphs used in the models have special properties such as
— min-max (in)equalities of certain parameters;
— cycles and chords;
— separator properties;
— distance properties;
— elimination orderings of the vertex set;
— composition/decomposition properties, recursive constructions;
— intersection, containment, or overlap models or measured variants of them;
— tree structure in many variants (reflected by related hypergraphs and matrices).
To efficiently solve such basic algorithmic problems as graph coloring, maximum independent set/maximum clique, Steiner tree, and dominating set, it is extremely important to know the structural properties of the graphs under consideration. A typical and classical example is the class of chordal graphs: every cycle of length at least four has at least one chord. These graphs have many different characterizations and thus appear in almost every chapter of this survey.
There are (at least) two main groups of graph properties that are helpful for designing polynomial-time algorithms:
— Graphs that fulfill certain min-max equalities such as Konig's theorem for bipartite graphs and Dilworth's theorem for partial orders. This approach leads to perfect graphs that have many nice algorithmic consequences.
— Graphs that generalize tree properties (trees of vertices or trees of hyperedges), since many problems are easy to solve on trees. Of course the problems again become hard on these generalizations if the graphs are "too far" from trees.
Of course the survey is also restricted to the basic properties; characterizations and inclusions of a collection of graph classes that seem to be important cannot exhaustively present the current knowledge. In particular, it is not. possible to discuss the complexity of selected algorithmic graph problems on as many classes as was done in [631]; for several problems there are separate monographs on the algorithmic behavior of the problem on special graph classes; see, for instance, [706] for the traveling salesman problem. It is sometimes hard to decide whether an algorithmically oriented paper using special graphs should be included in the survey. We try to include only those papers that describe interesting structural properties of the classes. We are not able to include all of these several thousand papers and apologize for the omitted ones, which could turn out to be important. The same holds true for the papers on special graph classes not included here due to space restrictions or due to our lack of knowledge. In particular, we do not describe the worlds of directed graphs, infinite graphs, and random graphs. Good sources for more information on infinite graphs are [505, 312, 1023], and a good source for random graphs is [125].
Basic Concepts.
Perfection, Generalized Perfection, and Related Concepts.
Cycles, Chords, and Bridges.
Models and Interactions.
Vertex and Edge Orderings.
Posets.
Forbidden Subgraphs.
Hypergraphs and Graphs.
Matrices and Polyhedra.
Distance Properties.
Algebraic Compositions and Recursive Definitions.
Decompositions and Cutsets.
Threshold Graphs and Related Concepts 1.
The Strong Perfect Graph Conjecture.
Скачать / Download

Комментарии


Смотрите также


Spinrad J. Graph theory

Spinrad J. Graph theory

разное
245 pages.

It seems to me that it may be the appropriate time to submit my book, with tentative title Efficient Graph Representations, to a publisher. It is not completely polished at this point, but to polish it up before getting comments from referees which might change substantial sections of the book seems a bit mi...
13.06.2011 в 17:55 1.06 Мб 13 раз
Chung F.R.K. Lectures on Spectral Graph Theory

Chung F.R.K. Lectures on Spectral Graph Theory

разное
Eigenvalues and the Laplacian of a graph. The Laplacian and eigenvalues. Basic facts about the spectrum of a graph. Eigenvalues of weighted graphs. Eigenvalues and random walks. Isoperimetric problems. History. The Cheeger constant of a graph. The edge expansion of a graph. The vertex expansion of a graph. A characterization of ...
01.12.2011 в 01:27 190.11 Кб 8 раз
Erd?s P., Hajnal A., M?t? A., Rado R. Combinatorial Set Theory. Partition Relations for Cardinals

Erd?s P., Hajnal A., M?t? A., Rado R. Combinatorial Set Theory. Partition Relations for Cardinals

разное
Издательство North-Holland, 1984, -342 pp.

Ramsey's classical theorem in its simplest form, published in 1930, says that if we put the edges of an infinite complete graph into two classes, then there will be an infinite complete subgraph all edges of which belong to the same class. The partition calculus developed as a ...
04.10.2011 в 01:42 2.26 Мб 6 раз
Hartsfield N., Ringel G. Pearls in Graph Theory: A Comprehensive Introduction

Hartsfield N., Ringel G. Pearls in Graph Theory: A Comprehensive Introduction

разное
Academic Press, 1994. - 249 pages.

Improved by more than a dozen new exercises, an augmented section on labeling, the simplification of many proofs, and corrections suggested by classroom users and reviewers, this delightful text on graph theory retains and strengthens the appealing features of the original edition. It ...
14.05.2011 в 02:21 2.11 Мб 13 раз
McKee T.A., McMorris F.R. Topics in Intersection Graph Theory

McKee T.A., McMorris F.R. Topics in Intersection Graph Theory

разное
Society for Industrial and Applied Mathematics, 1999, -214 pp.

Intersection graphs provide theory to underlie much of graph theory. They epitomize graph-theoretic structure and have their own distinctive concepts and emphasis. They subsume concepts as standard as line graphs and as nonstandard as tolerance graphs. They ...
31.01.2012 в 01:13 1.25 Мб 10 раз
Chartrand G., Lesniak L. Graphs and Digraphs

Chartrand G., Lesniak L. Graphs and Digraphs

разное
Издательство Chapman and Hall/CRC Press, 1996, -429 pp.

Graph theory is a major area of combinatorics, and during recent decades, graph theory has developed into a major area of mathematics. In addition to its growing interest and importance as a mathematical subject, it has applications to many fields, including comput...
26.10.2011 в 00:12 2.67 Мб 8 раз
Capobianco M., Moluzzo J.C. Examples and Counterexamples in Graph Theory

Capobianco M., Moluzzo J.C. Examples and Counterexamples in Graph Theory

разное
North-Holland, 1978. - 270 pages.

It is a real pleasure, indeed an honor, for me to have been invited by Mike Capobianco and John Molluzzo to write an introduction to this imaginative and valuable addition to graph theory. Let me therefore present a few of my thoughts on the current status of graph theory and how their ...
16.03.2011 в 23:40 12.91 Мб 15 раз
Gross J.L., Yellen J. (editors) Handbook of Graph Theory

Gross J.L., Yellen J. (editors) Handbook of Graph Theory

разное
CRC, 2003. - 1192 pages.

The Handbook of Graph Theory is the most comprehensive single-source guide to graph theory ever published. Best-selling authors Jonathan Gross and Jay Yellen assembled an outstanding team of experts to contribute overviews of more than 50 of the most significant topics in graph theory-including ...
01.01.2011 в 19:39 9.22 Мб 20 раз
Kaufmann M., Wagner D. (editors) Drawing Graphs: Methods and Models

Kaufmann M., Wagner D. (editors) Drawing Graphs: Methods and Models

разное
Springer, 2001. - 326 pages.

Graph drawing comprises all aspects of visualizing structural relations between objects. The range of topics dealt with extends from graph theory, graph algorithms, geometry, and topology to visual languages, visual perception, and information visualization, and to computer-human interactio...
12.09.2011 в 13:18 11.12 Мб 11 раз
Diestel R. Graph Theory

Diestel R. Graph Theory

разное
Springer, 2005. - 410 pages.

The third edition of this standard textbook of modern graph theory has been carefully revised, updated, and substantially extended. Covering all its major recent developments it can be used both as a reliable textbook for an introductory course and as a graduate text: on each topic it covers...
01.01.2011 в 04:12 2.43 Мб 12 раз