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

DOI10.1007/3-540-60084-1_68MaRDI QIDQ4645172zbMATH OpenOpenAlexFDO

Authors Andreas Parra, Petra Scheffler

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

interval graphchordal graphminimal separatormaximal cliquemaximal chain

Mathematics Subject Classification ID

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

Recommendations

• Minimal vertex separators of chordal graphs
• Minimal relative separators of chordal graphs
• scientific article; zbMATH DE number 1305094
• A linear time algorithm to list the minimal separators of chordal graphs
• Minimal separators of 2-chordal graphs
• One-phase algorithm for the determination of minimal vertex separators of chordal graphs
• A simple algorithm to generate the minimal separators and the maximal cliques of a chordal graph
• scientific article; zbMATH DE number 1796975
• Minimal vertex separators and new characterizations for dually chordal graphs
• On minimal vertex separators of dually chordal graphs: properties and characterizations

Cites work

• scientific article; zbMATH DE number 432839 (Why is no real title available?)
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 4147519 (Why is no real title available?)
• scientific article; zbMATH DE number 3896983 (Why is no real title available?)
• scientific article; zbMATH DE number 3908482 (Why is no real title available?)
• scientific article; zbMATH DE number 1354123 (Why is no real title available?)
• scientific article; zbMATH DE number 566078 (Why is no real title available?)
• scientific article; zbMATH DE number 1414319 (Why is no real title available?)
• A linear time algorithm for finding tree-decompositions of small treewidth
• Bipartite permutation graphs
• Complexity of Finding Embeddings in a k-Tree
• Computing the Minimum Fill-In is NP-Complete
• Easy problems for tree-decomposable graphs
• Interval dimension is a comparability invariant
• Matrix multiplication via arithmetic progressions
• On powers of \(m\)-trapezoid graphs
• On rigid circuit graphs
• The Pathwidth and Treewidth of Cographs
• The Transitive Reduction of a Directed Graph
• Trapezoid graphs and their coloring
• Treewidth and Pathwidth of Permutation Graphs
• Treewidth of Circular-Arc Graphs
• Treewidth. Computations and approximations
• Triangulating multitolerance graphs

Cited in

(11)

• On the minimum chordal completion polytope
• Minimal elimination of planar graphs
• Minimal elimination ordering for graphs of bounded degree
• 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
• A simple algorithm to generate the minimal separators and the maximal cliques of a chordal graph
• Characterizations and algorithmic applications of chordal graph embeddings
• Tree decompositions with small cost
• On treewidth and minimum fill-in of asteroidal triple-free graphs
• Representing a concept lattice by a graph
• Separator orders in interval, cocomparability, and AT-free graphs

This page was built for publication: How to use the minimal separators of a graph for its chordal triangulation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4645172)