Computing minimal triangulations in time O(n^ n) = o(n^2.376)

MaRDI QIDQ2921757zbMATH OpenFDO

Authors Pinar Heggernes, Jan Arne Telle, Yngve Villanger

Publication date 13 October 2014

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Extremal problems in graph theory (05C35)

Recommendations

• Computing Minimal Triangulations in Time O(nalpha log n) = o(n2.376)
• Fast minimal triangulation algorithm using minimum degree criterion
• scientific article; zbMATH DE number 1947421
• A wide-range algorithm for minimal triangulation from an arbitrary ordering
• scientific article; zbMATH DE number 1305489

Cited in

(15)

• Characterizing and computing minimal cograph completions
• Computing Minimal Triangulations in Time O(nalpha log n) = o(n2.376)
• Minimal interval completion through graph exploration
• A wide-range algorithm for minimal triangulation from an arbitrary ordering
• Minimal fill in O(\(n^{2.69}\)) time
• Fast minimal triangulation algorithm using minimum degree criterion
• Characterizing and Computing Minimal Cograph Completions
• Triangulation and clique separator decomposition of claw-free graphs
• The minimum degree heuristic and the minimal triangulation process.
• Minimal comparability completions of arbitrary graphs
• 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)
• scientific article; zbMATH DE number 1947421 (Why is no real title available?)
• scientific article; zbMATH DE number 2079402 (Why is no real title available?)

This page was built for publication: Computing minimal triangulations in time \(O(n^{\alpha \log n}) = o(n^{2.376})\)

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