ALGORITHMIC GRAPH THEORY AND PERFECT GRAPHS SECOND EDITIONpdf电子书版本下载

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

ALGORITHMIC GRAPH THEORY AND PERFECT GRAPHS SECOND EDITIONPDF格式电子书版下载

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

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

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

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

CHAPTER 1 Graph Theoretic Foundations 1

1.Basic Definitions and Notations 1

2.Intersection Graphs 9

3.Interval Graphs—A Sneak Preview of the Notions Coming Up 13

4.Summary 17

Exercises 18

Bibliography 20

CHAPTER 2 The Design of Efficient Algorithms 22

1.The Complexity of Computer Algorithms 22

2.Data Structures 31

3.How to Explore a Graph 37

4.Transitive Tournaments and Topological Sorting 42

Exercises 45

Bibliography 48

CHAPTER 3 Perfect Graphs 51

1.The Star of the Show 51

2.The Perfect Graph Theorem 53

3.p-Critical and Partitionable Graphs 58

4.A Polyhedral Characterization of Perfect Graphs 62

5.A Polyhedral Characterization of p-Critical Graphs 65

6.The Strong Perfect Graph Conjecture 71

Exercises 75

Bibliography 77

CHAPTER 4 Triangulated Graphs 81

1.Introduction 81

2.Characterizing Triangulated Graphs 81

3.Recognizing Triangulated Graphs by Lexicographic Breadth-First Search 84

4.The Complexity of Recognizing Triangulated Graphs 87

5.Triangulated Graphs as Intersection Graphs 91

6.Triangulated Graphs Are Perfect 94

7.Fast Algorithms for the COLORING，CLIQUE， STABLE SET， and CLIQUE-COVER Problems on Triangulated Graphs 98

Exercises 100

Bibliography 102

CHAPTER 5 Comparability Graphs 105

1.Γ-Chains and Implication Classes 105

2.Uniquely Partially Orderable Graphs 109

3.The Number of Transitive Orientations 113

4.Schemes and G-Decompositions—An Algorithm for Assigning Transitive Orientations 120

5.The 1*-Matroid of a Graph 124

6.The Complexity of Comparability Graph Recognition 129

7.Coloring and Other Problems on Comparability Graphs 132

8.The Dimension of Partial Orders 135

Exercises 139

Bibliography 142

CHAPTER 6 Split Graphs 149

1.An Introduction to Chapters 6-8： Interval，Permutation， and Split Graphs 149

2.Characterizing Split Graphs 149

3.Degree Sequences and Split Graphs 152

Exercises 155

Bibliography 156

CHAPTER 7 Permutation Graphs 157

1.Introduction 157

2.Characterizing Permutation Graphs 158

3.Permutation Labelings 160

4.Applications 162

5.Sorting a Permutation Using Queues in Parallel 164

Exercises 168

Bibliography 169

CHAPTER 8 Interal Graphs 171

1.How It All Started 171

2.Some Characterizations of Interval Graphs 172

3.The Complexity of Consecutive l’s Testing 175

4.Applications of Interval Graphs 181

5.Preference and Indifference 185

6.Circular-Arc Graphs 188

Exercises 193

Bibliography 197

CHAPTER 9 Superperfect Graphs 203

1.Coloring Weighted Graphs 203

2.Superperfection 206

3.An Infinite Class of Superperfect Noncom parability Graphs 209

4.When Does Superperfect Equal Comparability？ 212

5.Composition of Superperfect Graphs 214

6.A Representation Using the Consecutive l’s Property 215

Exercises 218

Bibliography 218

CHAPTER 10 Threshold Graphs 219

1.The Threshold Dimension 219

2.Degree Partition of Threshold Graphs 223

3.A Characterization Using Permutations 227

4.An Application to Synchronizing Parallel Processes 229

Exercises 231

Bibliography 234

CHAPTER 11 Not So Perfect Graphs 235

1.Sorting a Permutation Using Stacks in Parallel 235

2.Intersecting Chords of a Circle 237

3.Overlap Graphs 242

4.Fast Algorithms for Maximum Stable Set and Maximum Clique of These Not So Perfect Graphs 244

5.A Graph Theoretic Characterization of Overlap Graphs 248

Exercises 251

Bibliography 253

CHAPTER 12 Perfect Gaussian Elimination 254

1.Perfect Elimination Matrices 254

2.Symmetric Matrices 256

3.Perfect Elimination Bipartite Graphs 259

4.Chordal Bipartite Graphs 261

Exercises 264

Bibliography 266

Appendix 269

A.A Small Collection of NP-Complete Problems 269

B.An Algorithm for Set Union， Intersection，Difference， and Symmetric Difference of Two Subsets 270

C.Topological Sorting： An Example of Algorithm 2.4 271

D.An Illustration of the Decomposition Algorithm 273

E.The Properties P.E.B.， C.B.，（P.E.B.）’，（C.B.）’ Illustrated 273

F.The Properties C， C —， T， T — llustrated 275

Epilogue 2004 277

Index 307