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)

zbMATH Keywords

matrix multiplicationchordal graphminimal 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)

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

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)