Computing Minimal Triangulations in Time O(nalpha log n) = o(n2.376)

DOI10.1137/S0895480104445010zbMath1105.05066MaRDI QIDQ5470799

Pinar Heggernes, Jan Arne Telle, Yngve Villanger

Publication date: 1 June 2006

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

chordal graphmatrix multiplicationminimal fill

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (20)

Minimal triangulations of graphs: a survey ⋮ Linear-time minimal cograph editing ⋮ An introduction to clique minimal separator decomposition ⋮ An \(\mathcal O(n^2)\)-time algorithm for the minimal interval completion problem ⋮ Organizing the atoms of the clique separator decomposition into an atom tree ⋮ Revisiting Decomposition by Clique Separators ⋮ Fully dynamic algorithm for chordal graphs with \(O(1)\) query-time and \(O(n^2)\) update-time ⋮ An \(O(n^2)\) time algorithm for the minimal permutation completion problem ⋮ Tree decomposition and discrete optimization problems: a survey ⋮ Minimal proper interval completions ⋮ Treewidth computations. I: Upper bounds ⋮ Minimal split completions ⋮ A note on minimal d-separation trees for structural learning ⋮ Fast minimal triangulation algorithm using minimum degree criterion ⋮ Simple algorithms for minimal triangulation of a graph and backward selection of a decomposable Markov network ⋮ Faster and enhanced inclusion-minimal cograph completion ⋮ Single-edge monotonic sequences of graphs and linear-time algorithms for minimal completions and deletions ⋮ An $$\mathcal {O}(n^2)$$ Time Algorithm for the Minimal Permutation Completion Problem ⋮ Efficiently decomposing, recognizing and triangulating hole-free graphs without diamonds ⋮ Unnamed Item

This page was built for publication: Computing Minimal Triangulations in Time O(nalpha log n) = o(n2.376)