A LINEAR-TIME ALGORITHM FOR ISOMORPHISM OF GRAPHS OF BOUNDED AVERAGE GENUS

被引：12

作者：

CHEN, JN

机构：

来源：

SIAM JOURNAL ON DISCRETE MATHEMATICS | 1994年 / 7卷 / 04期

关键词：

ALGORITHM; GRAPH ISOMORPHISM; GRAPH IMBEDDING;

D O I：

10.1137/S0895480191196769

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

A structure theorem is proved for the class of graphs of bounded average genus, which leads to a linear-time algorithm for isomorphism of such graphs.

引用

页码：614 / 631

页数：18

共 21 条

[1] KURATOWSKI-TYPE THEOREMS FOR AVERAGE GENUS [J].

CHEN, J ;

GROSS, JL .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1993, 57 (01) :100-121

[2]

CHEN J, 1994, IN PRESS GRAPH THEOR

[3]

CHEN J, 1993, LECTURE NOTES COMPUT, V657, P103

[4] LIMIT POINTS FOR AVERAGE GENUS .1. 3-CONNECTED AND 2-CONNECTED SIMPLICIAL GRAPHS [J].

CHEN, JN ;

GROSS, JL .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1992, 55 (01) :83-103

[5] LIMIT POINTS FOR AVERAGE GENUS .2. 2-CONNECTED NONSIMPLICIAL GRAPHS [J].

CHEN, JN ;

GROSS, JL .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1992, 56 (01) :108-129

[6]

FILOTTI IS, 1980, 12TH P ACM S THEOR C, P236

[7]

FURST M, 1980, 80426 CORN U COMP SC

[8]

Garey M. R., 1979, COMPUTERS INTRACTABI

[9]

Gross J. L., 1987, TOPOLOGICAL GRAPH TH

[10] HIERARCHY FOR IMBEDDING-DISTRIBUTION INVARIANTS OF A GRAPH [J].

GROSS, JL ;

FURST, ML .

JOURNAL OF GRAPH THEORY, 1987, 11 (02) :205-220

← 1 2 3 →