Minimal triangulations of graphs: a survey
type: Item
instance of: scholarly article
title: Minimal triangulations of graphs: a survey
zbMATH Open document ID: 1086.05069
author: Pinar Heggernes
published in: Discrete Mathematics
publication date: 2006-03-29T00:00:00Z
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 5016268
zbMATH Keywords: Chordal graphs
zbMATH Keywords: minimal fill
zbMATH Keywords: triangulation algorithms
zbMATH Keywords: characterizations
describes a project that uses: symrcm
MaRDI profile type: Publication
full work available at URL: j.disc.2005.12.003
OpenAlex ID: W1981917097
cites work: An efficient algorithm for finding a two-pair, and its applications
cites work: Complexity of Finding Embeddings in a k-Tree
cites work: A fast algorithm for finding an edge-maximal subgraph with a TR-formative coloring
cites work: On the Desirability of Acyclic Database Schemes
cites work: Q4252378
cites work: Maximum cardinality search for computing minimal triangulations of graphs
cites work: Separability generalizes Dirac's theorem
cites work: GENERATING ALL THE MINIMAL SEPARATORS OF A GRAPH
cites work: A wide-range algorithm for minimal triangulation from an arbitrary ordering
cites work: Graph-Theoretic Concepts in Computer Science
cites work: Algorithms and Computation
cites work: A practical algorithm for making filled graphs minimal
cites work: Q4288578
cites work: Q4291429
cites work: Treewidth and Minimum Fill-in on d-Trapezoid Graphs
cites work: Safe separators for treewidth
cites work: Treewidth and minimum fill-in: Grouping the minimal separators
cites work: Listing all potential maximal cliques of a graph
cites work: A linear time algorithm for minimum fill-in and treewidth for distance hereditary graphs
cites work: A characterisation of rigid circuit graphs
cites work: Fixed-parameter tractability of graph modification problems for hereditary properties
cites work: NC algorithms for recognizing chordal graphs and k trees
cites work: Chordal completions of planar graphs
cites work: Matrix multiplication via arithmetic progressions
cites work: Asteroidal Triple-Free Graphs
cites work: Q4373676
cites work: Minimal elimination of planar graphs
cites work: Minimal elimination ordering for graphs of bounded degree
cites work: An efficient parallel algorithm for the minimal elimination ordering (MEO) of an arbitrary graph
cites work: Q3138901
cites work: Maximal chordal subgraphs
cites work: On rigid circuit graphs
cites work: Chordal graph recognition is in NC
cites work: Automata, Languages and Programming
cites work: Incidence matrices and interval graphs
cites work: `` Strong '' NP-Completeness Results
cites work: The intersection graphs of subtrees in trees are exactly the chordal graphs
cites work: Nested Dissection of a Regular Finite Element Mesh
cites work: Q3664299
cites work: Q3328583
cites work: Tolerance graphs
cites work: Q3271426
cites work: Computing Minimal Triangulations in Time O(nalpha log n) = o(n2.376)
cites work: Q4411390
cites work: Counting clique trees and computing perfect elimination schemes in parallel
cites work: Q4252412
cites work: Tractability of Parameterized Completion Problems on Chordal, Strongly Chordal, and Proper Interval Graphs
cites work: Listing all Minimal Separators of a Graph
cites work: On the structure of graphs with bounded asteroidal number
cites work: On treewidth and minimum fill-in of asteroidal triple-free graphs
cites work: Minimal fill in O(\(n^{2.69}\)) time
cites work: Domination on Cocomparability Graphs
cites work: Q4734791
cites work: Representation of a finite graph by a set of intervals on the real line
cites work: Equivalent Sparse Matrix Reordering by Elimination Tree Rotations
cites work: The Role of Elimination Trees in Sparse Factorization
cites work: Modular decomposition and transitive orientation
cites work: Triangulating graphs without asteroidal triples
cites work: A Polynomial Approximation Algorithm for the Minimum Fill-In Problem
cites work: Complexity classification of some edge modification problems
cites work: A Fast Algorithm for Finding an Optimal Ordering for Vertex Elimination on a Graph
cites work: Minimal triangulation of a graph and optimal pivoting order in a sparse matrix

Minimal triangulations of graphs: a survey (cites work)
cites work: Characterizations and algorithmic applications of chordal graph embeddings

Minimal triangulations of graphs: a survey (cites work)
cites work: The Use of Linear Graphs in Gauss Elimination

Minimal triangulations of graphs: a survey (cites work)
cites work: Minimal orderings revisited

Minimal triangulations of graphs: a survey (cites work)
cites work: Graph minors. II. Algorithmic aspects of tree-width

Minimal triangulations of graphs: a survey (cites work)
cites work: Q5683627

Minimal triangulations of graphs: a survey (cites work)
cites work: Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs

Minimal triangulations of graphs: a survey (cites work)
cites work: Edge‐maximal triangulated subgraphs and heuristics for the maximum clique problem

Minimal triangulations of graphs: a survey (cites work)
cites work: Computing the Minimum Fill-In is NP-Complete

Minimal triangulations of graphs: a survey (DOI)
DOI: 10.1016/J.DISC.2005.12.003