How to use the minimal separators of a graph for its chordal triangulation

DOI10.1007/3-540-60084-1_68zbMath1412.68171OpenAlexW1533693718MaRDI QIDQ4645172

Petra Scheffler, Andreas Parra

Publication date: 10 January 2019

Published in: Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-60084-1_68

zbMATH Keywords

maximal chainchordal graphinterval graphmaximal cliqueminimal separator

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items

Representing a concept lattice by a graph, Minimal elimination of planar graphs, Characterizations and algorithmic applications of chordal graph embeddings, On treewidth and minimum fill-in of asteroidal triple-free graphs, Creating non-minimal triangulations for use in inference in mixed stochastic/deterministic graphical models, A linear time algorithm for minimum fill-in and treewidth for distance hereditary graphs, Separator orders in interval, cocomparability, and AT-free graphs, Tree decompositions with small cost, Minimal elimination ordering for graphs of bounded degree, Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On rigid circuit graphs
• Interval dimension is a comparability invariant
• Matrix multiplication via arithmetic progressions
• Bipartite permutation graphs
• Trapezoid graphs and their coloring
• Treewidth. Computations and approximations
• Triangulating multitolerance graphs
• On powers of \(m\)-trapezoid graphs
• Easy problems for tree-decomposable graphs
• Complexity of Finding Embeddings in a k-Tree
• Computing the Minimum Fill-In is NP-Complete
• Treewidth of Circular-Arc Graphs
• The Pathwidth and Treewidth of Cographs
• Treewidth and Pathwidth of Permutation Graphs
• A linear time algorithm for finding tree-decompositions of small treewidth
• The Transitive Reduction of a Directed Graph