A wide-range algorithm for minimal triangulation from an arbitrary ordering

被引:29
作者
Berry, A
Bordat, JP
Heggernes, P [1 ]
Simonet, G
Villanger, Y
机构
[1] Univ Bergen, Dept Informat, N-5020 Bergen, Norway
[2] Univ Clermont Ferrand, CNRS,UMR 6158, LIMOS, Ensemble Sci Cezeaux, F-63170 Clermont Ferrand, France
[3] LIRMM, F-34392 Montpellier, France
来源
JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC | 2006年 / 58卷 / 01期
关键词
D O I
10.1016/j.jalgor.2004.07.001
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
We present a new algorithm, called LB-Triang, which computes minimal triangulations. We give both a straightforward 0 (nm') time implementation and a more involved 0 (nm) time implementation, thus matching the best known algorithms for this problem. Our algorithm is based on a process by Lekkerkerker and Boland for recognizing chordal graphs which checks in an arbitrary order whether the minimal separators contained in each vertex neighborhood are cliques. LB-Triang checks each vertex for this property and adds edges whenever necessary to make each vertex obey this property. As the vertices can be processed in any order, LB-Triang is able to compute any minimal triangulation of a given graph, which makes it significantly different from other existing triangulation techniques. We examine several interesting and useful properties of this algorithm, and give some experimental results. (C) 2004 Elsevier Inc. All rights reserved.
引用
收藏
页码:33 / 66
页数:34
相关论文
共 31 条
  • [1] AHO AV, 1974, DESIGN ANAL COMPUTER, P71
  • [2] [Anonymous], 1981, COMPUTER SOLUTION LA
  • [3] ON THE DESIRABILITY OF ACYCLIC DATABASE SCHEMES
    BEERI, C
    FAGIN, R
    MAIER, D
    YANNAKAKIS, M
    [J]. JOURNAL OF THE ACM, 1983, 30 (03) : 479 - 513
  • [4] Maximum cardinality search for computing minimal triangulations of graphs
    Berry, A
    Blair, JRS
    Heggernes, P
    Peyton, BW
    [J]. ALGORITHMICA, 2004, 39 (04) : 287 - 298
  • [5] BERRY A, 1999, P 10 ANN ACM SIAM S, pS860
  • [6] BERRY A, 1998, THESIS LIRMM MONTPEL
  • [7] BERRY A, 2000, NORDIC J COMPUTING, V7, P164
  • [8] A practical algorithm for making filled graphs minimal
    Blair, JRS
    Heggernes, P
    Telle, JA
    [J]. THEORETICAL COMPUTER SCIENCE, 2001, 250 (1-2) : 125 - 141
  • [9] Bodlaender H. L., 1993, Acta Cybernetica, V11, P1
  • [10] CHORDAL COMPLETIONS OF PLANAR GRAPHS
    CHUNG, FRK
    MUMFORD, D
    [J]. JOURNAL OF COMBINATORIAL THEORY SERIES B, 1994, 62 (01) : 96 - 106