EFFICIENT GRAPH REPRESENTATIONSpdf电子书版本下载

点此进入-本书在线PDF格式电子书下载【推荐-云解压-方便快捷】直接下载PDF格式图书。移动端-PC端通用
种子下载[BT下载速度快] 温馨提示：（请使用BT下载软件FDM进行下载）软件下载地址页 直链下载[便捷但速度慢]   [在线试读本书]   [在线获取解压码]

EFFICIENT GRAPH REPRESENTATIONSPDF格式电子书版下载

下载的文件为RAR压缩包。需要使用解压软件进行解压得到PDF格式图书。

建议使用BT下载工具Free Download Manager进行下载,简称FDM(免费,没有广告,支持多平台）。本站资源全部打包为BT种子。所以需要使用专业的BT下载软件进行下载。如 BitComet qBittorrent uTorrent等BT下载工具。迅雷目前由于本站不是热门资源。不推荐使用！后期资源热门了。安装了迅雷也可以迅雷进行下载！

（文件页数 要大于 标注页数，上中下等多册电子书除外）

注意：本站所有压缩包均有解压码： 点击下载压缩包解压工具

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