EFFICIENT GRAPH REPRESENTATIONSPDF|Epub|txt|kindle电子书版本网盘下载

EFFICIENT GRAPH REPRESENTATIONSPDF格式电子书版下载

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

Explanatory Remarks1

Chapter 1.Introduction5

1.1.Graph Theory Background and Terminology6

1.2.Algorithm Background and Terminology6

1.3.Representation Background8

1.4.Example of a Nice Representation11

1.5.Overview of Problems in Graph Representation12

1.6.Exercises15

Chapter 2.Implicit Representation17

2.1.Implicit Representation and Universal Graphs21

2.2.Generalized Implicit Representation22

2.3.Representations with Very Short Labels23

2.4.Distance Labeling of Graphs25

2.5.Exercises27

Chapter 3.Intersection and Containment Representations31

3.1.Chordality and Transitive Orientation31

3.2.Techniques for Interval Graphs33

3.3.Generalizations of Interval Graphs34

3.4.Permutation Graphs and Generalizations38

3.5.Containment Representations41

3.6.Overlap Representations42

3.7.Generalized Intersection Models44

3.8.Perfect Graphs46

3.9.Exercises47

Chapter 4.Real Numbers in Graph Representations53

4.1.Warren’s Theorem54

4.2.Continuous Nongeometric Variables56

4.3.Decidability Results57

4.4.Exercises57

Chapter 5.Classes Which use Global Information59

5.1.Paths in Trees59

5.2.Chordal Comparability Graphs60

5.3.Fill-in Schemes65

5.4.Closure Operations66

5.5.Weakly Chordal Graphs67

5.6.Other Fill-in Schemes68

5.7.Exercises68

Chapter 6.Visibility Graphs73

6.1.Counting Visibility Graphs74

6.2.Clique Cover Representation74

6.3.Induced Visibility Graphs76

6.4.Optimization on Visibility Graphs80

6.5.Line of Sight Graphs and Other Variants80

6.6.Exercises81

Chapter 7.Intersection of Graph Classes85

7.1.Some Fundamental Properties85

7.2.Intersections of Fundamental Properties87

7.3.Weakly Chordal Comparability Graphs88

7.4.Other Generalized Classes90

7.5.Observations Regarding AT-free co-AT-free Graphs91

7.6.Open Problems on the Generalized Classes94

7.7.Exercises95

Chapter 8. Graph Classes Defined by Forbidden Subgraphs97

8.1.Cographs97

8.2.Classes Which are too Large to have Efficient Representations100

8.3.Relation Between Recognition Problems105

8.4.Classes defined by Forbidding Sets of Induced Subgraphs105

8.5.Dilworth Number and Poset Width107

8.6.Exercises109

Chapter 9.Chordal Bipartite Graphs111

9.1.I-free Matrices111

9.2.Counting and Representation112

9.3.Characterizations118

9.4.Recognition120

9.5.Optimization Problems on Chordal Bipartite Graphs123

9.6.Variants of Chordal Bipartite Graphs125

9.7.Subclasses of Chordal Bipartite Graphs126

9.8.Perfect Elimination Bipartite Graphs130

9.9.Bipartite Graphs with Forbidden Induced Subgraphs131

9.10. Exercises132

Chapter 10.Matrices135

10.1. Small Forbidden Classes of Matrices135

10.2. Linear Matrices136

10.3. Forbidden 2 by 2 Identity Matrices138

10.4. Forbidding（10 10）139

10.5. Other Classes of Interest142

10.6. The Problems of Counting and Representation142

10.7. Other Matrix Properties145

10.8. Exercises145

Chapter 11.Decomposition149

11.1.Substitution Decomposition and Vertex Partitioning149

11.2.Join Decomposition160

11.3.Recursively Decomposable Graphs163

11.4.Clique-width and NLC-width164

11.5.Clique Separator Decomposition167

11.6.Skew Partition170

11.7.2-Join174

11.8.Exercises175

Chapter 12.Elimination Schemes181

12.1.Distance Hereditary Graphs181

12.2.Strongly Chordal Graphs182

12.3.k-Simplicial Elimination Schemes184

12.4.Doubly and Dually Chordal Graphs185

12.5.Exercises187

Chapter 13.Recognition Algorithms191

13.1.Chordal Graphs191

13.2.Interval Graphs193

13.3.Circular-Arc Graph Recognition197

13.4.Restrictions on Intervals and Arcs204

13.5.Trapezoid Graphs and Related Classes208

13.6.Circle Graphs212

13.7.Circular Permutation Graphs217

13.8.Weakly Chordal Graphs218

13.9.Paths in Trees219

13.10. NP-complete Classes222

13.11.Open Classes224

13.12.Exercises224

Chapter 14. Robust Algorithms for Optimization Problems231

14.1.Robust Algorithms which are Faster Than Recognition233

14.2.Problems Helped by a Representation241

14.3.Open Problems for Robust Algorithms247

14.4.Complexity Issues249

14.5.Exercises252

Chapter 15.Characterization and Construction257

15.1.Chordal Graphs257

15.2.Unit Interval Graphs259

15.3.Unit Circular-Arc Graphs260

15.4.Construction Problem for NP-complete Classes261

15.5.Exercises262

Chapter 16.Applications265

16.1.Computational Biology265

16.2.Networks268

16.3.Programming Languages272

16.4.A Cautionary Tale272

16.5.Exercises273

Glossary277

Survey of Results on Graph Classes303

Bibliography319

Index337