Minimal triangulations of graphs: a survey

DOI10.1016/j.disc.2005.12.003zbMath1086.05069OpenAlexW1981917097MaRDI QIDQ819823

Publication date: 29 March 2006

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disc.2005.12.003

zbMATH Keywords

characterizations Chordal graphs minimal fill triangulation algorithms

Mathematics Subject Classification ID

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

Related Items (62)

An integer programming model for the Minimum Interval Graph Completion Problem ⋮ Enumerating minimal connected dominating sets in graphs of bounded chordality ⋮ Linear-Time Generation of Random Chordal Graphs ⋮ Search-space size in contraction hierarchies ⋮ Decomposition Methods for Sparse Matrix Nearness Problems ⋮ Graphs with maximal induced matchings of the same size ⋮ An introduction to clique minimal separator decomposition ⋮ Polynomially bounding the number of minimal separators in graphs: reductions, sufficient conditions, and a dichotomy theorem ⋮ Triangulability of convex graphs and convex skewness ⋮ Objective Bayesian Nets for Integrating Consistent Datasets ⋮ Two characterisations of the minimal triangulations of permutation graphs ⋮ An $\mathcal O(n^2)$-time algorithm for the minimal interval completion problem ⋮ Computational study of a branching algorithm for the maximum $k$-cut problem ⋮ Enumeration of minimal tropical connected sets ⋮ Large Induced Subgraphs via Triangulations and CMSO ⋮ Organizing the atoms of the clique separator decomposition into an atom tree ⋮ A new global algorithm for max-cut problem with chordal sparsity ⋮ Computing and listing avoidable vertices and paths ⋮ How to Use Planarity Efficiently: New Tree-Decomposition Based Algorithms ⋮ Supersolvable saturated matroids and chordal graphs ⋮ Computing and listing avoidable vertices and paths ⋮ On Listing, Sampling, and Counting the Chordal Graphs with Edge Constraints ⋮ Unnamed Item ⋮ Revisiting Decomposition by Clique Separators ⋮ Fully dynamic algorithm for chordal graphs with $O(1)$ query-time and $O(n^2)$ update-time ⋮ Fully dynamic representations of interval graphs ⋮ Bayesian graph selection consistency under model misspecification ⋮ An $O(n^2)$ time algorithm for the minimal permutation completion problem ⋮ Faster parameterized algorithms for \textsc{Minimum Fill-in} ⋮ The software to analyze the states of complex systems under uncertainty based on fuzzy belief network models ⋮ Minimum Fill-In and Treewidth of Split+ ke and Split+ kv Graphs ⋮ Searching for better fill-in ⋮ Chordal-TSSOS: A Moment-SOS Hierarchy That Exploits Term Sparsity with Chordal Extension ⋮ Efficiently enumerating minimal triangulations ⋮ Bayes linear analysis for ordinary differential equations ⋮ Treewidth computations. I: Upper bounds ⋮ Minimal split completions ⋮ Minimum fill-in of sparse graphs: kernelization and approximation ⋮ A note on minimal d-separation trees for structural learning ⋮ Minimum fill-in and treewidth of split $+ ke$ and split $+kv$ graphs ⋮ Dynamic programming and planarity: improved tree-decomposition based algorithms ⋮ On the complexity of computing treelength ⋮ Fast minimal triangulation algorithm using minimum degree criterion ⋮ On listing, sampling, and counting the chordal graphs with edge constraints ⋮ Simple algorithms for minimal triangulation of a graph and backward selection of a decomposable Markov network ⋮ Finding cut-vertices in the square roots of a graph ⋮ Subexponential parameterized algorithms and kernelization on almost chordal graphs ⋮ Improving the linear relaxation of maximum $k$-cut with semidefinite-based constraints ⋮ Standard imsets for undirected and chain graphical models ⋮ Unnamed Item ⋮ On a property of minimal triangulations ⋮ Exploiting variable sparsity in computing equilibria of biological dynamical systems by triangular decomposition ⋮ An $$\mathcal {O}(n^2)$$ Time Algorithm for the Minimal Permutation Completion Problem ⋮ On the Number of Minimal Separators in Graphs ⋮ Avoidable vertices and edges in graphs: existence, characterization, and applications ⋮ Bayesian networks: the minimal triangulations of a graph ⋮ SIMPLIFIED NUMERICAL FORM OF UNIVERSAL FINITE TYPE INVARIANT OF GAUSS WORDS ⋮ A Network Design Problem with Two-Edge Matching Failures ⋮ Tree decompositions and social graphs ⋮ Efficiently decomposing, recognizing and triangulating hole-free graphs without diamonds ⋮ Unnamed Item ⋮ Modifying a graph using vertex elimination

Uses Software

symrcm

Cites Work

This page was built for publication: Minimal triangulations of graphs: a survey