Fast minimal triangulation algorithm using minimum degree criterion

DOI10.1016/J.TCS.2011.04.022MaRDI QIDQ551209zbMATH OpenOpenAlexFDO

Authors Mauro Mezzini

Publication date 14 July 2011

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2011.04.022

zbMATH Keywords

minimum degreechordal graphsminimal triangulations

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• 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)
• The minimum degree heuristic and the minimal triangulation process.
• A wide-range algorithm for minimal triangulation from an arbitrary ordering
• scientific article; zbMATH DE number 1305489

Cites work

• scientific article; zbMATH DE number 554762 (Why is no real title available?)
• A practical algorithm for making filled graphs minimal
• A wide-range algorithm for minimal triangulation from an arbitrary ordering
• Algorithmic Aspects of Vertex Elimination on Graphs
• Characterizations and algorithmic applications of chordal graph embeddings
• Computing Minimal Triangulations in Time O(nalpha log n) = o(n2.376)
• Computing the Minimum Fill-In is NP-Complete
• Convexity in Graphs and Hypergraphs
• Fully dynamic algorithms for chordal graphs and split graphs
• Maximum cardinality search for computing minimal triangulations of graphs
• Minimal triangulations of graphs: a survey
• On the Desirability of Acyclic Database Schemes
• Representation of a finite graph by a set of intervals on the real line
• Sequential and parallel triangulating algorithms for elimination game and new insights on minimum degree
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• Simple algorithms for minimal triangulation of a graph and backward selection of a decomposable Markov network
• Single-edge monotonic sequences of graphs and linear-time algorithms for minimal completions and deletions
• The Evolution of the Minimum Degree Ordering Algorithm
• The minimum degree heuristic and the minimal triangulation process.

Cited in

(12)

• Computing minimal triangulations in time \(O(n^{\alpha \log n}) = o(n^{2.376})\)
• The minimum degree heuristic and the minimal triangulation process.
• Sequential and parallel triangulating algorithms for elimination game and new insights on minimum degree
• Minimum degree triangulation for rectangular domains
• Simple algorithms for minimal triangulation of a graph and backward selection of a decomposable Markov network
• scientific article; zbMATH DE number 1305489 (Why is no real title available?)
• Fully dynamic algorithm for chordal graphs with \(O(1)\) query-time and \(O(n^2)\) update-time
• Minimum Average Distance Triangulations
• An algorithm for constructing locally optimal min-max triangulation
• A wide-range algorithm for minimal triangulation from an arbitrary ordering
• scientific article; zbMATH DE number 1947421 (Why is no real title available?)
• The sum-product algorithm: algebraic independence and computational aspects

This page was built for publication: Fast minimal triangulation algorithm using minimum degree criterion

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