A linear time algorithm to list the minimal separators of chordal graphs

被引：10

作者：

Chandran, LS ^{[1
]}

Grandoni, F ^{[1
]}

机构：

[1] Max Planck Inst Informat, D-66123 Saarbrucken, Germany

来源：

DISCRETE MATHEMATICS | 2006年 / 306卷 / 03期

关键词：

minimal separator; chordal graph; perfect elimination ordering;

D O I：

10.1016/j.disc.2005.12.010

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

Kumar and Madhavan [Minimal vertex separators of chordal graphs, Discrete Appl. Math. 89 (1998) 155-168] gave a linear time algorithm to list all the minimal separators of a chordal graph. In this paper we give another linear time algorithm for the same purpose. While the algorithm of Kumar and Madhavan requires that a specific type of PEO, namely the MCS PEO is computed first, our algorithm works with any PEO. This is interesting when we consider the fact that there are other popular methods such as Lex BFS to compute a PEO for a given chordal graph. (c) 2006 Elsevier B.V. All rights reserved.

引用

页码：351 / 358

页数：8

共 18 条

[1]

[Anonymous], 1993, EFFICIENT ALGORITHMS

[2] CUT-SET GRAPH AND SYSTEMATIC GENERATION OF SEPARATING SETS [J].

ARIYOSHI, H .

IEEE TRANSACTIONS ON CIRCUIT THEORY, 1972, CT19 (03) :233-&

[3]

Berry A., 2000, International Journal of Foundations of Computer Science, V11, P397, DOI 10.1142/S0129054100000211

[4] TREEWIDTH AND PATHWIDTH OF PERMUTATION GRAPHS [J].

BODLAENDER, HL ;

KLOKS, T ;

KRATSCH, D .

SIAM JOURNAL ON DISCRETE MATHEMATICS, 1995, 8 (04) :606-616

[5]

Chandran LS, 2001, LECT NOTES COMPUT SC, V2108, P308

[6] Generating and characterizing the perfect elimination orderings of a chordal graph [J].

Chandran, LS ;

Ibarra, L ;

Ruskey, F ;

Sawada, J .

THEORETICAL COMPUTER SCIENCE, 2003, 307 (02) :303-317

[7]

Cormen T. H., 1990, INTRO ALGORITHMS

[8]

Golumbic MC., 1980, Algorithmic Graph Theory and Perfect Graphs

[9] FINDING ALL MINIMUM-SIZE SEPARATING VERTEX SETS IN A GRAPH [J].

KANEVSKY, A .

NETWORKS, 1993, 23 (06) :533-541

[10]

Kloks T., 1994, Treewidth. Computations and approximations, DOI 10.1007/BFb0045375

← 1 2 →