- 作 者：
- 出 版 社：AMERICAN MATHEMATICAL SOCIETY
- 出版年份：2003
- ISBN：0821828150
- 标注页数：343 页
- PDF页数：350 页
请阅读订购服务说明与试读!
订购服务说明
1、本站所有的书默认都是PDF格式，该格式图书只能阅读和打印，不能再次编辑。
2、除分上下册或者多册的情况下，一般PDF页数一定要大于标注页数才建议下单购买。【本资源350 ≥343页】
图书下载及付费说明
1、所有的电子图书为PDF格式，支持电脑、手机、平板等各类电子设备阅读；可以任意拷贝文件到不同的阅读设备里进行阅读。
2、电子图书在提交订单后一般半小时内处理完成,最晚48小时内处理完成。(非工作日购买会延迟)
3、所有的电子图书都是原书直接扫描方式制作而成。
Explanatory Remarks 1
Chapter 1.Introduction 5
1.1.Graph Theory Background and Terminology 6
1.2.Algorithm Background and Terminology 6
1.3.Representation Background 8
1.4.Example of a Nice Representation 11
1.5.Overview of Problems in Graph Representation 12
1.6.Exercises 15
Chapter 2.Implicit Representation 17
2.1.Implicit Representation and Universal Graphs 21
2.2.Generalized Implicit Representation 22
2.3.Representations with Very Short Labels 23
2.4.Distance Labeling of Graphs 25
2.5.Exercises 27
Chapter 3.Intersection and Containment Representations 31
3.1.Chordality and Transitive Orientation 31
3.2.Techniques for Interval Graphs 33
3.3.Generalizations of Interval Graphs 34
3.4.Permutation Graphs and Generalizations 38
3.5.Containment Representations 41
3.6.Overlap Representations 42
3.7.Generalized Intersection Models 44
3.8.Perfect Graphs 46
3.9.Exercises 47
Chapter 4.Real Numbers in Graph Representations 53
4.1.Warren’s Theorem 54
4.2.Continuous Nongeometric Variables 56
4.3.Decidability Results 57
4.4.Exercises 57
Chapter 5.Classes Which use Global Information 59
5.1.Paths in Trees 59
5.2.Chordal Comparability Graphs 60
5.3.Fill-in Schemes 65
5.4.Closure Operations 66
5.5.Weakly Chordal Graphs 67
5.6.Other Fill-in Schemes 68
5.7.Exercises 68
Chapter 6.Visibility Graphs 73
6.1.Counting Visibility Graphs 74
6.2.Clique Cover Representation 74
6.3.Induced Visibility Graphs 76
6.4.Optimization on Visibility Graphs 80
6.5.Line of Sight Graphs and Other Variants 80
6.6.Exercises 81
Chapter 7.Intersection of Graph Classes 85
7.1.Some Fundamental Properties 85
7.2.Intersections of Fundamental Properties 87
7.3.Weakly Chordal Comparability Graphs 88
7.4.Other Generalized Classes 90
7.5.Observations Regarding AT-free co-AT-free Graphs 91
7.6.Open Problems on the Generalized Classes 94
7.7.Exercises 95
Chapter 8. Graph Classes Defined by Forbidden Subgraphs 97
8.1.Cographs 97
8.2.Classes Which are too Large to have Efficient Representations 100
8.3.Relation Between Recognition Problems 105
8.4.Classes defined by Forbidding Sets of Induced Subgraphs 105
8.5.Dilworth Number and Poset Width 107
8.6.Exercises 109
Chapter 9.Chordal Bipartite Graphs 111
9.1.I-free Matrices 111
9.2.Counting and Representation 112
9.3.Characterizations 118
9.4.Recognition 120
9.5.Optimization Problems on Chordal Bipartite Graphs 123
9.6.Variants of Chordal Bipartite Graphs 125
9.7.Subclasses of Chordal Bipartite Graphs 126
9.8.Perfect Elimination Bipartite Graphs 130
9.9.Bipartite Graphs with Forbidden Induced Subgraphs 131
9.10. Exercises 132
Chapter 10.Matrices 135
10.1. Small Forbidden Classes of Matrices 135
10.2. Linear Matrices 136
10.3. Forbidden 2 by 2 Identity Matrices 138
10.4. Forbidding（10 10） 139
10.5. Other Classes of Interest 142
10.6. The Problems of Counting and Representation 142
10.7. Other Matrix Properties 145
10.8. Exercises 145
Chapter 11.Decomposition 149
11.1.Substitution Decomposition and Vertex Partitioning 149
11.2.Join Decomposition 160
11.3.Recursively Decomposable Graphs 163
11.4.Clique-width and NLC-width 164
11.5.Clique Separator Decomposition 167
11.6.Skew Partition 170
11.7.2-Join 174
11.8.Exercises 175
Chapter 12.Elimination Schemes 181
12.1.Distance Hereditary Graphs 181
12.2.Strongly Chordal Graphs 182
12.3.k-Simplicial Elimination Schemes 184
12.4.Doubly and Dually Chordal Graphs 185
12.5.Exercises 187
Chapter 13.Recognition Algorithms 191
13.1.Chordal Graphs 191
13.2.Interval Graphs 193
13.3.Circular-Arc Graph Recognition 197
13.4.Restrictions on Intervals and Arcs 204
13.5.Trapezoid Graphs and Related Classes 208
13.6.Circle Graphs 212
13.7.Circular Permutation Graphs 217
13.8.Weakly Chordal Graphs 218
13.9.Paths in Trees 219
13.10. NP-complete Classes 222
13.11.Open Classes 224
13.12.Exercises 224
Chapter 14. Robust Algorithms for Optimization Problems 231
14.1.Robust Algorithms which are Faster Than Recognition 233
14.2.Problems Helped by a Representation 241
14.3.Open Problems for Robust Algorithms 247
14.4.Complexity Issues 249
14.5.Exercises 252
Chapter 15.Characterization and Construction 257
15.1.Chordal Graphs 257
15.2.Unit Interval Graphs 259
15.3.Unit Circular-Arc Graphs 260
15.4.Construction Problem for NP-complete Classes 261
15.5.Exercises 262
Chapter 16.Applications 265
16.1.Computational Biology 265
16.2.Networks 268
16.3.Programming Languages 272
16.4.A Cautionary Tale 272
16.5.Exercises 273
Glossary 277
Survey of Results on Graph Classes 303
Bibliography 319
Index 337