Atnaujinkite slapukų nuostatas

Algorithmic Graph Theory and Perfect Graphs 2nd edition, Volume 57 [Kietas viršelis]

4.00/5 (4 ratings by Goodreads)
(University of Haifa, Isreal.)
  • Formatas: Hardback, 340 pages, aukštis x plotis: 240x165 mm, weight: 660 g
  • Serija: Annals of Discrete Mathematics
  • Išleidimo metai: 04-Feb-2004
  • Leidėjas: North-Holland
  • ISBN-10: 0444515305
  • ISBN-13: 9780444515308
Kitos knygos pagal šią temą:
Algorithmic Graph Theory and Perfect Graphs 2nd edition, Volume 57Didesnis paveikslėlis
  • Formatas: Hardback, 340 pages, aukštis x plotis: 240x165 mm, weight: 660 g
  • Serija: Annals of Discrete Mathematics
  • Išleidimo metai: 04-Feb-2004
  • Leidėjas: North-Holland
  • ISBN-10: 0444515305
  • ISBN-13: 9780444515308
Kitos knygos pagal šią temą:
Pastovi nuoroda: https://www.kriso.lt/db/9780444515308.html
Raktažodžiai:
Algorithmic Graph Theory and Perfect Graphs, first published in 1980, has become the classic introduction to the field. This new Annals edition continues to convey the message that intersection graph models are a necessary and important tool for solving real-world problems. It remains a stepping stone from which the reader may embark on one of many fascinating research trails.

The past twenty years have been an amazingly fruitful period of research in algorithmic graph theory and structured families of graphs. Especially important have been the theory and applications of new intersection graph models such as generalizations of permutation graphs and interval graphs. These have lead to new families of perfect graphs and many algorithmic results. These are surveyed in the new Epilogue chapter in this second edition.

New edition of the "Classic" book on the topic
Wonderful introduction to a rich research area
Leading author in the field of algorithmic graph theory
Beautifully written for the new mathematician or computer scientist
Comprehensive treatment

Recenzijos

"... this volume is, as was its predecessor, an excellent and motivating introduction to the world of perfect graphs" --D. de Werra (CH-LSNP; Lausanne) in: Mathematical Reviews

Daugiau informacijos

Covers many applications associated with classes of perfect graphs.
Foreword 2004 xiii
Foreword xv
Preface xvii
Acknowledgments xix
List of Symbols
xxi
Corrections and Errata xxiii
Graph Theoretic Foundations
Basic Definitions and Notations
1(8)
Intersection Graphs
9(4)
Interval Graphs---A Sneak Preview of the Notions Coming Up
13(4)
Summary
17(5)
Exercises
18(2)
Bibliography
20(2)
The Design of Efficient Algorithms
The Complexity of Computer Algorithms
22(9)
Data Structures
31(6)
How to Explore a Graph
37(5)
Transitive Tournaments and Topological Sorting
42(9)
Exercises
45(3)
Bibliography
48(3)
Perfect Graphs
The Star of the Show
51(2)
The Perfect Graph Theorem
53(5)
p-Critical and Partitionable Graphs
58(4)
A Polyhedral Characterization of Perfect Graphs
62(3)
A Polyhedral Characterization of p-Critical Graphs
65(6)
The Strong Perfect Graph Conjecture
71(10)
Exercises
75(2)
Bibliography
77(4)
Triangulated Graphs
Introduction
81(1)
Characterizing Triangulated Graphs
81(3)
Recognizing Triangulated Graphs by Lexicographic Breadth-First Search
84(3)
The Complexity of Recognizing Triangulated Graphs
87(4)
Triangulated Graphs as Intersection Graphs
91(3)
Triangulated Graphs Are Perfect
94(4)
Fast Algorithms for the Coloring, Clique, Stable Set, and Clique-Cover Problems on Triangulated Graphs
98(7)
Exercises
100(2)
Bibliography
102(3)
Comparability Graphs
Γ-Chains and Implication Classes
105(4)
Uniquely Partially Orderable Graphs
109(4)
The Number of Transitive Orientations
113(7)
Schemes and G-Decompositions---An Algorithm for Assigning Transitive Orientations
120(4)
The Γ*-Matroid of a Graph
124(5)
The Complexity of Comparability Graph Recognition
129(3)
Coloring and Other Problems on Comparability Graphs
132(3)
The Dimension of Partial Orders
135(14)
Exercises
139(3)
Bibliography
142(7)
Split Graphs
An Introduction to
Chapters 6--8: Interval, Permutation, and Split Graphs
149(1)
Characterizing Split Graphs
149(3)
Degree Sequences and Split Graphs
152(5)
Exercises
155(1)
Bibliography
156(1)
Permutation Graphs
Introduction
157(1)
Characterizing Permutation Graphs
158(2)
Permutation Labelings
160(2)
Applications
162(2)
Sorting a Permutation Using Queues in Parallel
164(7)
Exercises
168(1)
Bibliography
169(2)
Interval Graphs
How It All Started
171(1)
Some Characterizations of Interval Graphs
172(3)
The Complexity of Consecutive 1's Testing
175(6)
Applications of Interval Graphs
181(4)
Preference and Indifference
185(3)
Circular-Arc Graphs
188(15)
Exercises
193(4)
Bibliography
197(6)
Superperfect Graphs
Coloring Weighted Graphs
203(3)
Superperfection
206(3)
An Infinite Class of Superperfect Noncomparability Graphs
209(3)
When Does Superperfect Equal Comparability?
212(2)
Composition of Superperfect Graphs
214(1)
A Representation Using the Consecutive 1's Property
215(4)
Exercises
218(1)
Bibliography
218(1)
Threshold Graphs
The Threshold Dimension
219(4)
Degree Partition of Threshold Graphs
223(4)
A Characterization Using Permutations
227(2)
An Application to Synchronizing Parallel Processes
229(6)
Exercises
231(3)
Bibliography
234(1)
Not So Perfect Graphs
Sorting a Permutation Using Stacks in Parallel
235(2)
Intersecting Chords of a Circle
237(5)
Overlap Graphs
242(2)
Fast Algorithms for Maximum Stable Set and Maximum Clique of These Not So Perfect Graphs
244(4)
A Graph Theoretic Characterization of Overlap Graphs
248(6)
Exercises
251(2)
Bibliography
253(1)
Perfect Gaussian Elimination
Perfect Elimination Matrices
254(2)
Symmetric Matrices
256(3)
Perfect Elimination Bipartite Graphs
259(2)
Chordal Bipartite Graphs
261(8)
Exercises
264(2)
Bibliography
266(3)
Appendix
A. A Small Collection of NP-Complete Problems
269(1)
B. An Algorithm for Set Union, Intersection, Difference, and Symmetric Difference of Two Subsets
270(1)
C. Topological Sorting: An Example of Algorithm 2.4
271(2)
D. An Illustration of the Decomposition Algorithm
273(1)
E. The Properties P.E.B., C.B., (P.E.B.)', (C.B.)' Illustrated
273(2)
F. The Properties C, C, T, T Illustrated
275(2)
Epilogue 2004 277(30)
Index 307