AN O(N2) ALGORITHM FOR UNDIRECTED SPLIT DECOMPOSITION

被引：26

作者：

MA, TH

SPINRAD, J

机构：

[1] Department of Computer Science, Vanderbilt University, Nashville

来源：

JOURNAL OF ALGORITHMS | 1994年 / 16卷 / 01期

关键词：

D O I：

10.1006/jagm.1994.1007

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

The time complexity of the undirected split, or join, decomposition of a graph is reduced from Ω(n3) to O(n2). In a companion paper, this result is used to improve the time bound for recognizing circle graphs. © 1994 Academic Press, Inc.

引用

页码：145 / 160

页数：16

共 15 条

[1] DISTANCE-HEREDITARY GRAPHS [J].

BANDELT, HJ ;

MULDER, HM .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1986, 41 (02) :182-208

[2] DIGRAPH DECOMPOSITIONS AND EULERIAN SYSTEMS [J].

BOUCHET, A .

SIAM JOURNAL ON ALGEBRAIC AND DISCRETE METHODS, 1987, 8 (03) :323-337

[3] REDUCING PRIME GRAPHS AND RECOGNIZING CIRCLE GRAPHS [J].

BOUCHET, A .

COMBINATORICA, 1987, 7 (03) :243-254

[4] COMPLEMENT REDUCIBLE GRAPHS [J].

CORNEIL, DG ;

LERCHS, H ;

BURLINGHAM, LS .

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

[5] DECOMPOSITION OF DIRECTED-GRAPHS [J].

CUNNINGHAM, WH .

SIAM JOURNAL ON ALGEBRAIC AND DISCRETE METHODS, 1982, 3 (02) :214-228

[6] RECOGNIZING CIRCLE GRAPHS IN POLYNOMIAL-TIME [J].

GABOR, CP ;

SUPOWIT, KJ ;

HSU, WL .

JOURNAL OF THE ACM, 1989, 36 (03) :435-473

[7]

Golumbic M. C., 1980, ALGORITHMIC GRAPH TH

[8] COMPLETELY SEPARABLE GRAPHS [J].

HAMMER, PL ;

MAFFRAY, F .

DISCRETE APPLIED MATHEMATICS, 1990, 27 (1-2) :85-99

[9]

HSU WL, UNPUB RECOGNITION IS

[10]

Mohring R. H., 1985, Annals of Operations Research, V4, P195, DOI 10.1007/BF02022041

← 1 2 →