Minimal fill in O(n^2.69) time

DOI10.1016/J.DISC.2005.12.009MaRDI QIDQ819828zbMATH OpenOpenAlexFDO

Authors Dieter Kratsch, Jeremy P. Spinrad

Publication date 29 March 2006

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.disc.2005.12.009

zbMATH Keywords

triangulation

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Fast Computation of Minimal Fill Inside A Given Elimination Ordering
• A practical algorithm for making filled graphs minimal
• Computing minimal triangulations in time \(O(n^{\alpha \log n}) = o(n^{2.376})\)
• Computing Minimal Triangulations in Time O(nalpha log n) = o(n2.376)
• Minimal orderings revisited

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1305489 (Why is no real title available?)
• scientific article; zbMATH DE number 2079402 (Why is no real title available?)
• scientific article; zbMATH DE number 1775391 (Why is no real title available?)
• A Fast Algorithm for Finding an Optimal Ordering for Vertex Elimination on a Graph
• A wide-range algorithm for minimal triangulation from an arbitrary ordering
• Algorithmic Aspects of Vertex Elimination on Directed Graphs
• Algorithmic Aspects of Vertex Elimination on Graphs
• Computing minimal triangulations in time \(O(n^{\alpha \log n}) = o(n^{2.376})\)
• Decomposition by clique separators
• Gaussian elimination is not optimal
• Matrix multiplication via arithmetic progressions
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• The Complexity of the Partial Order Dimension Problem
• The Use of Linear Graphs in Gauss Elimination

Cited in

(12)

• Organizing the atoms of the clique separator decomposition into an atom tree
• Minimal proper interval completions
• Minimal split completions
• Efficiently decomposing, recognizing and triangulating hole-free graphs without diamonds
• Minimal triangulations of graphs: a survey
• A practical algorithm for making filled graphs minimal
• An introduction to clique minimal separator decomposition
• Revisiting decomposition by clique separators
• Minimal comparability completions of arbitrary graphs
• Minimal orderings revisited
• Minimal elimination of planar graphs
• A note on minimal d-separation trees for structural learning

This page was built for publication: Minimal fill in O(\(n^{2.69}\)) time

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