Minimal triangulations of graphs: a survey
From MaRDI portal
Publication:819823
DOI10.1016/J.DISC.2005.12.003zbMATH Open1086.05069OpenAlexW1981917097MaRDI QIDQ819823FDOQ819823
Authors: Pinar Heggernes 
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
Recommendations
- A wide-range algorithm for minimal triangulation from an arbitrary ordering
- Characterizations and algorithmic applications of chordal graph embeddings
- scientific article; zbMATH DE number 1305489
- scientific article; zbMATH DE number 1305094
- Maximum cardinality search for computing minimal triangulations of graphs
Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)
Cites Work
- Title not available (Why is that?)
- Nested Dissection of a Regular Finite Element Mesh
- Fixed-parameter tractability of graph modification problems for hereditary properties
- Title not available (Why is that?)
- Modular decomposition and transitive orientation
- Incidence matrices and interval graphs
- Domination on Cocomparability Graphs
- Complexity of Finding Embeddings in a k-Tree
- Title not available (Why is that?)
- On the structure of graphs with bounded asteroidal number
- On rigid circuit graphs
- Matrix multiplication via arithmetic progressions
- The intersection graphs of subtrees in trees are exactly the chordal graphs
- Representation of a finite graph by a set of intervals on the real line
- Graph minors. II. Algorithmic aspects of tree-width
- Title not available (Why is that?)
- Asteroidal Triple-Free Graphs
- On the Desirability of Acyclic Database Schemes
- Title not available (Why is that?)
- Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
- `` Strong NP-Completeness Results
- Edge‐maximal triangulated subgraphs and heuristics for the maximum clique problem
- Maximal chordal subgraphs
- Listing all potential maximal cliques of a graph
- Treewidth and minimum fill-in: Grouping the minimal separators
- The Role of Elimination Trees in Sparse Factorization
- Computing the Minimum Fill-In is NP-Complete
- Tractability of Parameterized Completion Problems on Chordal, Strongly Chordal, and Proper Interval Graphs
- Listing all Minimal Separators of a Graph
- GENERATING ALL THE MINIMAL SEPARATORS OF A GRAPH
- Title not available (Why is that?)
- Complexity classification of some edge modification problems
- The Use of Linear Graphs in Gauss Elimination
- Title not available (Why is that?)
- Counting clique trees and computing perfect elimination schemes in parallel
- Characterizations and algorithmic applications of chordal graph embeddings
- On treewidth and minimum fill-in of asteroidal triple-free graphs
- A characterisation of rigid circuit graphs
- Triangulating graphs without asteroidal triples
- Title not available (Why is that?)
- Treewidth and Minimum Fill-in on d-Trapezoid Graphs
- Computing Minimal Triangulations in Time O(nalpha log n) = o(n2.376)
- Equivalent Sparse Matrix Reordering by Elimination Tree Rotations
- Separability generalizes Dirac's theorem
- A practical algorithm for making filled graphs minimal
- An efficient algorithm for finding a two-pair, and its applications
- Maximum cardinality search for computing minimal triangulations of graphs
- A wide-range algorithm for minimal triangulation from an arbitrary ordering
- Tolerance graphs
- Safe separators for treewidth
- Minimal fill in O(\(n^{2.69}\)) time
- Minimal triangulation of a graph and optimal pivoting order in a sparse matrix
- Title not available (Why is that?)
- The minimum degree heuristic and the minimal triangulation process.
- Chordal completions of planar graphs
- A linear time algorithm for minimum fill-in and treewidth for distance hereditary graphs
- A Polynomial Approximation Algorithm for the Minimum Fill-In Problem
- Minimal orderings revisited
- Automata, Languages and Programming
- A fast algorithm for finding an edge-maximal subgraph with a TR-formative coloring
- Chordal graph recognition is in NC
- An efficient parallel algorithm for the minimal elimination ordering (MEO) of an arbitrary graph
- Title not available (Why is that?)
- NC algorithms for recognizing chordal graphs and k trees
- A Fast Algorithm for Finding an Optimal Ordering for Vertex Elimination on a Graph
- Title not available (Why is that?)
- Title not available (Why is that?)
- Minimal elimination of planar graphs
- Algorithms and Computation
- Minimal elimination ordering for graphs of bounded degree
Cited In (71)
- Bisimplicial separators
- Enumeration of minimal tropical connected sets
- Objective Bayesian Nets for Integrating Consistent Datasets
- Supersolvable saturated matroids and chordal graphs
- Graphs with at most two moplexes
- A network design problem with two-edge matching failures
- Computing and listing avoidable vertices and paths
- A new global algorithm for max-cut problem with chordal sparsity
- Simplified numerical form of universal finite type invariant of Gauss words
- Computational study of a branching algorithm for the maximum \(k\)-cut problem
- An \(\mathcal O(n^2)\)-time algorithm for the minimal interval completion problem
- A Characterisation of the Minimal Triangulations of Permutation Graphs
- Decomposition methods for sparse matrix nearness problems
- Title not available (Why is that?)
- Bayesian graph selection consistency under model misspecification
- Bayesian networks: the minimal triangulations of a graph
- On the number of minimal separators in graphs
- Organizing the atoms of the clique separator decomposition into an atom tree
- Minimal split completions
- On a property of minimal triangulations
- Efficiently decomposing, recognizing and triangulating hole-free graphs without diamonds
- On listing, sampling, and counting the chordal graphs with edge constraints
- Triangulating planar graphs while minimizing the maximum degree
- Enumerating minimal connected dominating sets in graphs of bounded chordality
- Triangulability of convex graphs and convex skewness
- Title not available (Why is that?)
- Searching for better fill-in
- An \(\mathcal {O}(n^2)\) time algorithm for the minimal permutation completion problem
- Modifying a graph using vertex elimination
- On the Minimal Density of Triangles in Graphs
- Dynamic programming and planarity: improved tree-decomposition based algorithms
- An introduction to clique minimal separator decomposition
- Fully dynamic algorithm for chordal graphs with \(O(1)\) query-time and \(O(n^2)\) update-time
- Title not available (Why is that?)
- Search-space size in contraction hierarchies
- Fast minimal triangulation algorithm using minimum degree criterion
- On Listing, Sampling, and Counting the Chordal Graphs with Edge Constraints
- Revisiting decomposition by clique separators
- Subexponential parameterized algorithms and kernelization on almost chordal graphs
- On the complexity of computing treelength
- Bayes linear analysis for ordinary differential equations
- An improved lower bound on the minimum number of triangulations
- Improving the linear relaxation of maximum \(k\)-cut with semidefinite-based constraints
- Graphs with maximal induced matchings of the same size
- Simple algorithms for minimal triangulation of a graph and backward selection of a decomposable Markov network
- Treewidth computations. I: Upper bounds
- On the minimum chordal completion polytope
- The software to analyze the states of complex systems under uncertainty based on fuzzy belief network models
- Minimum fill-in of sparse graphs: kernelization and approximation
- How to Use Planarity Efficiently: New Tree-Decomposition Based Algorithms
- Efficiently enumerating minimal triangulations
- Exploiting variable sparsity in computing equilibria of biological dynamical systems by triangular decomposition
- Chordal-TSSOS: a moment-SOS hierarchy that exploits term sparsity with chordal extension
- The Minimum Number of Triangular Edges and a Symmetrization Method for Multiple Graphs
- Avoidable vertices and edges in graphs: existence, characterization, and applications
- Polynomially bounding the number of minimal separators in graphs: reductions, sufficient conditions, and a dichotomy theorem
- Finding cut-vertices in the square roots of a graph
- Standard imsets for undirected and chain graphical models
- Computing and listing avoidable vertices and paths
- Linear-time generation of random chordal graphs
- Faster parameterized algorithms for \textsc{Minimum Fill-in}
- Large Induced Subgraphs via Triangulations and CMSO
- Tree decompositions and social graphs
- An integer programming model for the minimum interval graph completion problem
- Title not available (Why is that?)
- Fully dynamic representations of interval graphs
- A note on minimal d-separation trees for structural learning
- An \(O(n^2)\) time algorithm for the minimal permutation completion problem
- Minimum Fill-In and Treewidth of Split+ ke and Split+ kv Graphs
- Minimum fill-in and treewidth of split \(+ ke\) and split \(+kv\) graphs
- Two characterisations of the minimal triangulations of permutation graphs
Uses Software
This page was built for publication: Minimal triangulations of graphs: a survey
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q819823)
