Simple algorithms for minimal triangulation of a graph and backward selection of a decomposable Markov network

DOI10.1016/j.tcs.2009.10.004zbMath1213.05251OpenAlexW2024773026MaRDI QIDQ2268854

Marina Moscarini, Mauro Mezzini

Publication date: 9 March 2010

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

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

zbMATH Keywords

chordal graphslearning decomposable modelsminimal triangulationsMarkov networks

Mathematics Subject Classification ID

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

Related Items (7)

Triangulability of convex graphs and convex skewness ⋮ Organizing the atoms of the clique separator decomposition into an atom tree ⋮ Fully dynamic algorithm for chordal graphs with \(O(1)\) query-time and \(O(n^2)\) update-time ⋮ Fast minimal triangulation algorithm using minimum degree criterion ⋮ Unnamed Item ⋮ Exploiting variable sparsity in computing equilibria of biological dynamical systems by triangular decomposition ⋮ Unnamed Item

Cites Work

• Minimal triangulations of graphs: a survey
• Existence of extensions and product extensions for discrete probability distributions
• A practical algorithm for making filled graphs minimal
• Maximum cardinality search for computing minimal triangulations of graphs
• 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
• Fast Computation of Minimal Fill Inside A Given Elimination Ordering
• 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)
• On Information and Sufficiency
• Unnamed Item

This page was built for publication: Simple algorithms for minimal triangulation of a graph and backward selection of a decomposable Markov network