THE PATHWIDTH AND TREEWIDTH OF COGRAPHS

被引：105

作者：

BODLAENDER, HL ^{[1
]}

MOHRING, RH ^{[1
]}

机构：

[1] TECH UNIV BERLIN,DEPT MATH,W-1000 BERLIN 12,GERMANY

来源：

SIAM JOURNAL ON DISCRETE MATHEMATICS | 1993年 / 6卷 / 02期

关键词：

GRAPH ALGORITHMS; COGRAPHS; TREEWIDTH; PATHWIDTH;

D O I：

10.1137/0406014

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

It is shown that the pathwidth of a cograph equals its treewidth, and a linear time algorithm to determine the pathwidth of a cograph and build a corresponding path-decomposition is given.

引用

页码：181 / 188

页数：8

共 23 条

[1] LINEAR TIME ALGORITHMS FOR NP-HARD PROBLEMS RESTRICTED TO PARTIAL K-TREES
ARNBORG, S
PROSKUROWSKI, A
[J]. DISCRETE APPLIED MATHEMATICS, 1989, 23 (01) : 11 - 24
[2] ARNBORG S, 1985, BIT, V25, P2, DOI 10.1007/BF01934985
[3] COMPLEXITY OF FINDING EMBEDDINGS IN A K-TREE
ARNBORG, S
CORNEIL, DG
PROSKUROWSKI, A
[J]. SIAM JOURNAL ON ALGEBRAIC AND DISCRETE METHODS, 1987, 8 (02): : 277 - 284
[4] BODLAENDER HL, 1991, LECT NOTES COMPUT SC, V510, P544
[5] BODLAENDER HL, 1988, LECT NOTES COMPUT SC, V317, P105
[6] BODLAENDER HL, 1986, RUUCS8622 U UTR DEP
[7] COMPLEMENT REDUCIBLE GRAPHS
CORNEIL, DG
LERCHS, H
BURLINGHAM, LS
[J]. DISCRETE APPLIED MATHEMATICS, 1981, 3 (03) : 163 - 174
[8] A LINEAR RECOGNITION ALGORITHM FOR COGRAPHS
CORNEIL, DG
PERL, Y
STEWART, LK
[J]. SIAM JOURNAL ON COMPUTING, 1985, 14 (04) : 926 - 934
[9] NONCONSTRUCTIVE TOOLS FOR PROVING POLYNOMIAL-TIME DECIDABILITY
FELLOWS, MR
LANGSTON, MA
[J]. JOURNAL OF THE ACM, 1988, 35 (03) : 727 - 739
[10] FELLOWS MR, 1988, 5TH P MIT C ADV RES, P315

← 1 2 3 →