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

DOI10.1137/S0895480104445010MaRDI QIDQ5470799zbMATH OpenFDO

Authors Pinar Heggernes, Jan Arne Telle, Yngve Villanger

Publication date 1 June 2006

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

Full work available at URL https://doi.org/10.1137/S0895480104445010

zbMATH Keywords

chordal graphmatrix multiplicationminimal fill

Mathematics Subject Classification ID

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

Recommendations

• Computing minimal triangulations in time \(O(n^{\alpha \log n}) = o(n^{2.376})\)
• An $O(n^2 \log n)$ Time Algorithm for the Minmax Angle Triangulation
• scientific article; zbMATH DE number 619546
• A Quadratic Time Algorithm for the Minmax Length Triangulation
• An O(n\log \log n)-Time Algorithm for Triangulating a Simple Polygon
• Efficiently enumerating minimal triangulations
• Polygon triangulation in \(O(n\log{}\log{}n)\) time with simple data structures
• Delaunay triangulations in O (sort( n )) time and more
• A quasi-polynomial time approximation scheme for minimum weight triangulation
• A quasi-polynomial time approximation scheme for minimum weight triangulation

Cited in

(28)

• Single-edge monotonic sequences of graphs and linear-time algorithms for minimal completions and deletions
• An introduction to clique minimal separator decomposition
• An \(O(n^2)\) time algorithm for the minimal permutation completion problem
• Maximum cardinality search for computing minimal triangulations of graphs
• Efficiently enumerating minimal triangulations
• Linear-time minimal cograph editing
• Simple algorithms for minimal triangulation of a graph and backward selection of a decomposable Markov network
• Efficiently decomposing, recognizing and triangulating hole-free graphs without diamonds
• Tree decomposition and discrete optimization problems: a survey
• An \(\mathcal {O}(n^2)\) time algorithm for the minimal permutation completion problem
• Computing minimal triangulations in time \(O(n^{\alpha \log n}) = o(n^{2.376})\)
• BetweenO(nm) andO(n^alpha)
• 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
• scientific article; zbMATH DE number 1947421 (Why is no real title available?)
• Fully dynamic algorithm for chordal graphs with \(O(1)\) query-time and \(O(n^2)\) update-time
• Revisiting decomposition by clique separators
• Triangulation and clique separator decomposition of claw-free graphs
• A wide-range algorithm for minimal triangulation from an arbitrary ordering
• Fast minimal triangulation algorithm using minimum degree criterion
• scientific article; zbMATH DE number 7053390 (Why is no real title available?)
• The minimum degree heuristic and the minimal triangulation process.
• Minimal triangulations of graphs: a survey
• Minimal fill in O(\(n^{2.69}\)) time
• Minimal proper interval completions
• Treewidth computations. I: Upper bounds
• Minimal split completions
• A note on minimal d-separation trees for structural learning

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5470799)