Fast minimal triangulation algorithm using minimum degree criterion

DOI10.1016/j.tcs.2011.04.022zbMath1220.05121OpenAlexW2002740543MaRDI QIDQ551209

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

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

Related Items (2)

Fully dynamic algorithm for chordal graphs with \(O(1)\) query-time and \(O(n^2)\) update-time ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Minimal triangulations of graphs: a survey
• Single-edge monotonic sequences of graphs and linear-time algorithms for minimal completions and deletions
• Characterizations and algorithmic applications of chordal graph embeddings
• 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
• Sequential and parallel triangulating algorithms for elimination game and new insights on minimum degree
• On the Desirability of Acyclic Database Schemes
• Representation of a finite graph by a set of intervals on the real line
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• Convexity in Graphs and Hypergraphs
• The Evolution of the Minimum Degree Ordering Algorithm
• Computing the Minimum Fill-In is NP-Complete
• Algorithmic Aspects of Vertex Elimination on Graphs
• Fully dynamic algorithms for chordal graphs and split graphs
• A wide-range algorithm for minimal triangulation from an arbitrary ordering
• Computing Minimal Triangulations in Time O(nalpha log n) = o(n2.376)
• Graph-Theoretic Concepts in Computer Science

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