THE PATHWIDTH AND TREEWIDTH OF COGRAPHS

被引：106

作者：

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 [J].

ARNBORG, S ;

PROSKUROWSKI, A .

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 [J].

ARNBORG, S ;

CORNEIL, DG ;

PROSKUROWSKI, A .

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 [J].

CORNEIL, DG ;

LERCHS, H ;

BURLINGHAM, LS .

DISCRETE APPLIED MATHEMATICS, 1981, 3 (03) :163-174

[8] A LINEAR RECOGNITION ALGORITHM FOR COGRAPHS [J].

CORNEIL, DG ;

PERL, Y ;

STEWART, LK .

SIAM JOURNAL ON COMPUTING, 1985, 14 (04) :926-934

[9] NONCONSTRUCTIVE TOOLS FOR PROVING POLYNOMIAL-TIME DECIDABILITY [J].

FELLOWS, MR ;

LANGSTON, MA .

JOURNAL OF THE ACM, 1988, 35 (03) :727-739

[10]

FELLOWS MR, 1988, 5TH P MIT C ADV RES, P315

← 1 2 3 →