Minimal triangulations of graphs: a survey
From MaRDI portal
Redirect page
Redirect to:
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
Cites work
- scientific article; zbMATH DE number 432771 (Why is no real title available?)
- scientific article; zbMATH DE number 3152801 (Why is no real title available?)
- scientific article; zbMATH DE number 3859178 (Why is no real title available?)
- scientific article; zbMATH DE number 3816913 (Why is no real title available?)
- scientific article; zbMATH DE number 1305489 (Why is no real title available?)
- scientific article; zbMATH DE number 1305520 (Why is no real title available?)
- scientific article; zbMATH DE number 554762 (Why is no real title available?)
- scientific article; zbMATH DE number 566078 (Why is no real title available?)
- scientific article; zbMATH DE number 1107728 (Why is no real title available?)
- scientific article; zbMATH DE number 1947421 (Why is no real title available?)
- scientific article; zbMATH DE number 4121482 (Why is no real title available?)
- scientific article; zbMATH DE number 3420184 (Why is no real title available?)
- A Fast Algorithm for Finding an Optimal Ordering for Vertex Elimination on a Graph
- A Polynomial Approximation Algorithm for the Minimum Fill-In Problem
- A characterisation of rigid circuit graphs
- A fast algorithm for finding an edge-maximal subgraph with a TR-formative coloring
- A linear time algorithm for minimum fill-in and treewidth for distance hereditary graphs
- A practical algorithm for making filled graphs minimal
- A wide-range algorithm for minimal triangulation from an arbitrary ordering
- Algorithms and Computation
- An efficient algorithm for finding a two-pair, and its applications
- An efficient parallel algorithm for the minimal elimination ordering (MEO) of an arbitrary graph
- Asteroidal Triple-Free Graphs
- Automata, Languages and Programming
- Characterizations and algorithmic applications of chordal graph embeddings
- Chordal completions of planar graphs
- Chordal graph recognition is in NC
- Complexity classification of some edge modification problems
- Complexity of Finding Embeddings in a k-Tree
- Computing Minimal Triangulations in Time O(nalpha log n) = o(n2.376)
- Computing the Minimum Fill-In is NP-Complete
- Counting clique trees and computing perfect elimination schemes in parallel
- Domination on Cocomparability Graphs
- Edge‐maximal triangulated subgraphs and heuristics for the maximum clique problem
- Equivalent Sparse Matrix Reordering by Elimination Tree Rotations
- Fixed-parameter tractability of graph modification problems for hereditary properties
- GENERATING ALL THE MINIMAL SEPARATORS OF A GRAPH
- Graph minors. II. Algorithmic aspects of tree-width
- Incidence matrices and interval graphs
- Listing all Minimal Separators of a Graph
- Listing all potential maximal cliques of a graph
- Matrix multiplication via arithmetic progressions
- Maximal chordal subgraphs
- Maximum cardinality search for computing minimal triangulations of graphs
- Minimal elimination of planar graphs
- Minimal elimination ordering for graphs of bounded degree
- Minimal fill in O(\(n^{2.69}\)) time
- Minimal orderings revisited
- Minimal triangulation of a graph and optimal pivoting order in a sparse matrix
- Modular decomposition and transitive orientation
- NC algorithms for recognizing chordal graphs and k trees
- Nested Dissection of a Regular Finite Element Mesh
- On rigid circuit graphs
- On the Desirability of Acyclic Database Schemes
- On the structure of graphs with bounded asteroidal number
- On treewidth and minimum fill-in of asteroidal triple-free graphs
- Representation of a finite graph by a set of intervals on the real line
- Safe separators for treewidth
- Separability generalizes Dirac's theorem
- Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
- The Role of Elimination Trees in Sparse Factorization
- The Use of Linear Graphs in Gauss Elimination
- The intersection graphs of subtrees in trees are exactly the chordal graphs
- The minimum degree heuristic and the minimal triangulation process.
- Tolerance graphs
- Tractability of Parameterized Completion Problems on Chordal, Strongly Chordal, and Proper Interval Graphs
- Treewidth and Minimum Fill-in on d-Trapezoid Graphs
- Treewidth and minimum fill-in: Grouping the minimal separators
- Triangulating graphs without asteroidal triples
- `` Strong NP-Completeness Results
Cited in
(75)- 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
- Minimum Fill-In and Treewidth of Split+ ke and Split+ kv Graphs
- A Characterisation of the Minimal Triangulations of Permutation Graphs
- Decomposition methods for sparse matrix nearness problems
- Bayesian graph selection consistency under model misspecification
- scientific article; zbMATH DE number 7651188 (Why is no real title available?)
- 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
- Bisimplicial separators
- Enumeration of minimal tropical connected sets
- Objective Bayesian Nets for Integrating Consistent Datasets
- The convex set forming game
- Minimal split completions
- A safeness condition for minimal separators based on vertex connectivity
- On a property of minimal triangulations
- Supersolvable saturated matroids and chordal graphs
- Efficiently decomposing, recognizing and triangulating hole-free graphs without diamonds
- On listing, sampling, and counting the chordal graphs with edge constraints
- Enumerating minimal connected dominating sets in graphs of bounded chordality
- Triangulating planar graphs while minimizing the maximum degree
- Triangulability of convex graphs and convex skewness
- Searching for better fill-in
- scientific article; zbMATH DE number 6469175 (Why is no real title available?)
- An \(\mathcal {O}(n^2)\) time algorithm for the minimal permutation completion problem
- Modifying a graph using vertex elimination
- Dynamic programming and planarity: improved tree-decomposition based algorithms
- On the Minimal Density of Triangles in Graphs
- Graphs with at most two moplexes
- Fully dynamic algorithm for chordal graphs with \(O(1)\) query-time and \(O(n^2)\) update-time
- Search-space size in contraction hierarchies
- An introduction to clique minimal separator decomposition
- Fast minimal triangulation algorithm using minimum degree criterion
- scientific article; zbMATH DE number 7053390 (Why is no real title available?)
- A network design problem with two-edge matching failures
- 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
- Computing and listing avoidable vertices and paths
- On the complexity of computing treelength
- Bayes linear analysis for ordinary differential equations
- Graphs with maximal induced matchings of the same size
- An improved lower bound on the minimum number of triangulations
- Improving the linear relaxation of maximum \(k\)-cut with semidefinite-based constraints
- Treewidth computations. I: Upper bounds
- Simple algorithms for minimal triangulation of a graph and backward selection of a decomposable Markov network
- The software to analyze the states of complex systems under uncertainty based on fuzzy belief network models
- On the minimum chordal completion polytope
- Bayesian model selection consistency for high-dimensional discrete graphical 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
- Standard imsets for undirected and chain graphical models
- Finding cut-vertices in the square roots of a graph
- Faster parameterized algorithms for \textsc{Minimum Fill-in}
- Computing and listing avoidable vertices and paths
- Simplified numerical form of universal finite type invariant of Gauss words
- Large Induced Subgraphs via Triangulations and CMSO
- A new global algorithm for max-cut problem with chordal sparsity
- Linear-time generation of random chordal graphs
- An integer programming model for the minimum interval graph completion problem
- Tree decompositions and social graphs
- scientific article; zbMATH DE number 1305094 (Why is no real title available?)
- A contraction-recursive algorithm for treewidth
- Fully dynamic representations of interval graphs
- A note on minimal d-separation trees for structural learning
- Minimum fill-in and treewidth of split \(+ ke\) and split \(+kv\) graphs
- Two characterisations of the minimal triangulations of permutation graphs
- An \(O(n^2)\) time algorithm for the minimal permutation completion problem
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)
