Generating and characterizing the perfect elimination orderings of a chordal graph

被引：22

作者：

Chandran, LS

Ibarra, L

Ruskey, F ^{[1
]}

Sawada, J

机构：

[1] Univ Victoria, Dept Comp Sci, Victoria, BC V8W 3P6, Canada

[2] Indian Inst Sci, Dept Comp Sci & Automat, Bangalore 560012, Karnataka, India

[3] Simon Fraser Univ, Dept Comp Sci, Burnaby, BC V5A 1S6, Canada

来源：

THEORETICAL COMPUTER SCIENCE | 2003年 / 307卷 / 02期

关键词：

perfect elimination ordering; chordal graphs gray code; antimatroid; 2-processor scheduling; Clique tree;

D O I：

10.1016/S0304-3975(03)00221-4

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We develop a constant time transposition "oracle" for the set of perfect elimination orderings of chordal graphs. Using this oracle, we can generate a Gray code of all perfect elimination orderings in constant amortized time using known results about antimatroids. Using clique trees, we show how the initialization of the algorithm can be performed in linear time. We also develop two new characterizations of perfect elimination orderings: one in terms of chordless paths, and the other in terms of minimal u-v separators. (C) 2003 Elsevier B.V. All rights reserved.

引用

页码：303 / 317

页数：15

共 17 条

[1]

BJORNER A, 1992, MATROID APPL

[2]

Blair Jean R. S., 1993, Graph theory and sparse matrix computation, P1, DOI [10.1007/978-1-4613-8369-7_1, DOI 10.1007/978-1-4613-8369-71]

[3]

Buneman P., 1974, Discrete Mathematics, V9, P205, DOI 10.1016/0012-365X(74)90002-8

[4]

Coffman E. G. Jr., 1972, Acta Informatica, V1, P200, DOI 10.1007/BF00288685

[5]

Dirac G. A., 1961, Abh. Math. Semin. Univ. Hambg, V25, P71, DOI [10.1007/BF02992776, DOI 10.1007/BF02992776]

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

FULKERSON, DR ;

GROSS, OA .

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

[7]

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

[8]

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

[9]

Korte B., 1991, GREEDOIDS

[10] Minimal vertex separators of chordal graphs [J].

Kumar, PS ;

Madhavan, CEV .

DISCRETE APPLIED MATHEMATICS, 1998, 89 (1-3) :155-168

← 1 2 →