Fast minimal triangulation algorithm using minimum degree criterion

DOI10.1016/J.TCS.2011.04.022zbMATH Open1220.05121OpenAlexW2002740543MaRDI QIDQ551209FDOQ551209

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

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

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)

Cites Work

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

Cited In (12)

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

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)