POLYNOMIAL ALGORITHMS FOR GRAPH ISOMORPHISM AND CHROMATIC INDEX ON PARTIAL K-TREES

被引：139

作者：

BODLAENDER, HL

机构：

[1] STATE UNIV UTRECHT,DEPT COMP SCI,3508 TB UTRECHT,NETHERLANDS

[2] MIT,COMP SCI LAB,CAMBRIDGE,MA 02139

来源：

JOURNAL OF ALGORITHMS | 1990年 / 11卷 / 04期

关键词：

D O I：

10.1016/0196-6774(90)90013-5

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

In this paper we show that graph isomorphism and chromatic index are solvable in polynomial time when restricted to the class of graphs with treewidth ≤ k (k a constant) (or equivalently, the class of partial k-trees). © 1990.

引用

页码：631 / 643

页数：13

共 24 条

[1] CHARACTERIZATION AND RECOGNITION OF PARTIAL 3-TREES [J].

ARNBORG, S ;

PROSKUROWSKI, A .

SIAM JOURNAL ON ALGEBRAIC AND DISCRETE METHODS, 1986, 7 (02) :305-314

[2] 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

[3]

ARNBORG S, 1985, BIT, V25, P2, DOI 10.1007/BF01934985

[4]

ARNBORG S, 1988, LECT NOTES COMPUT SC, V317, P38

[5] 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

[6]

ARNBORG S, 1988, IN PRESS J ALGORITHM

[7]

BODLAENDER HL, 1988, LECTURE NOTES COMPUT, V344, P1

[8]

BODLAENDER HL, 1988, RUUCS8829 U UTR DEP

[9]

BODLAENDER HL, 1987, P ICALP 88

[10]

BODLAENDER HL, 1986, RUUCS8622 U UTR DEP

← 1 2 3 →