The isomorphism problem for directed path graphs and for rooted directed path graphs

被引：22

作者：

Babel, L ^{[1
]}

Ponomarenko, IN ^{[1
]}

Tinhofer, G ^{[1
]}

机构：

[1] POMI,ST PETERSBURG 191011,RUSSIA

来源：

JOURNAL OF ALGORITHMS | 1996年 / 21卷 / 03期

关键词：

D O I：

10.1006/jagm.1996.0058

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

This paper deals with the isomorphism problem of directed path graphs and rooted directed path graphs. Both graph classes belong to the class of chordal graphs, and for both classes the relative complexity of the isomorphism problem is yet unknown. We prove that deciding isomorphism of directed path graphs is isomorphism complete, whereas for rooted directed path graphs we present a polynomial-time isomorphism algorithm. (C) 1996 Academic Press, Inc.

引用

页码：542 / 564

页数：23

共 27 条

[1]

[Anonymous], 1988, ZAP NAUCHN SEM LENIN, V174, P147

[2]

[Anonymous], 1979, CS7704 U WAT COMP SC

[3]

BABAI L, 1981, LECT NOTES COMPUTER, V117, P34

[4]

BABAI L, 1982, 14TH P ACM S THEOR C, P310

[5]

BOOTH KS, 1979, J ACM, V26, P183

[6] ON TESTING ISOMORPHISM OF PERMUTATION GRAPHS [J].

COLBOURN, CJ .

NETWORKS, 1981, 11 (01) :13-21

[7] COMPLEMENT REDUCIBLE GRAPHS [J].

CORNEIL, DG ;

LERCHS, H ;

BURLINGHAM, LS .

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

[8]

DIETZ P, 1984, 84628 TR CORN U

[9]

Fontet M., 1976, P 3 C AUT LANG PROGR, P411

[10]

Gavril F., 1974, Journal of Combinatorial Theory, Series B, V16, P47, DOI 10.1016/0095-8956(74)90094-X

← 1 2 3 →