LINEAR TIME ALGORITHM FOR DECIDING INTERVAL GRAPH ISOMORPHISM

被引：124

作者：

LUEKER, GS ^{[1
]}

BOOTH, KS ^{[1
]}

机构：

[1] UNIV WATERLOO, DEPT COMP SCI, WATERLOO N2L 3G1, ONTARIO, CANADA

来源：

JOURNAL OF THE ACM | 1979年 / 26卷 / 02期

关键词：

chordal graphs; graph isomorphism algonthms; intersection graphs; interval graphs; polynomial reduclinhty; rigid clrcmt graphs;

D O I：

10.1145/322123.322125

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

A graph is an interval graph tf and only if each of Its verttces can be associated with an interval on the real hne m such a way that two vertices are adjacent m the graph exactly when the corresponding mtervals have a nonempty mtersectmn An effictent algonthrn for testing tsomorpinsm of interval graphs ts unplemented using a data structure called a PQ-tree. The algorithm runs m O(n + e) steps for graphs having n vemces and e edges It is shown that for a somewhat larger class of graphs, namely the chordal graphs, lsomorpinsm is as hard as for general graphs. © 1979, ACM. All rights reserved.

引用

页码：183 / 195

页数：13

共 19 条

[1]

Aho A. V., 1974, DESIGN ANAL COMPUTER

[2]

[Anonymous], 1976, DISCRETE MATH MODELS

[3]

BOOTH K, 1977, CS7704 U WAT DEP COM

[4]

Booth K.S, 1975, THESIS U CALIFORNIA

[5]

BOOTH KS, 1977, UCRL51953

[6]

FISCHER M, COMMUNICATION

[7] INCIDENCE MATRICES AND INTERVAL GRAPHS [J].

FULKERSON, DR ;

GROSS, OA .

PACIFIC JOURNAL OF MATHEMATICS, 1965, 15 (03) :835-+

[8]

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

[9]

Gavril F., 1972, SIAM Journal on Computing, V1, P180, DOI 10.1137/0201013

[10]

HajuEs G., 1957, INT MATH NACHRICHTEN, V11, P65

← 1 2 →