An introduction to clique minimal separator decomposition
From MaRDI portal
Publication:1662549
Summary: This paper is a review which presents and explains the decomposition of graphs by clique minimal separators. The pace is leisurely, we give many examples and figures. Easy algorithms are provided to implement this decomposition. The historical and theoretical background is given, as well as sketches of proofs of the structural results involved.
Recommendations
Cites work
- A vertex incremental approach for maintaining chordality
- A wide-range algorithm for minimal triangulation from an arbitrary ordering
- Algorithmic Aspects of Vertex Elimination on Graphs
- Algorithms on clique separable graphs
- An algorithm for finding clique cut-sets
- Computing Minimal Triangulations in Time O(nalpha log n) = o(n2.376)
- Computing the Minimum Fill-In is NP-Complete
- Decomposition by clique separators
- scientific article; zbMATH DE number 432771 (Why is no real title available?)
- scientific article; zbMATH DE number 554762 (Why is no real title available?)
- Maximal label search algorithms to compute perfect and minimal elimination orderings
- Maximum cardinality search for computing minimal triangulations of graphs
- Minimal fill in O(\(n^{2.69}\)) time
- Minimal triangulations of graphs: a survey
- On clique separators, nearly chordal graphs, and the Maximum Weight Stable Set Problem
- On rigid circuit graphs
- Optimal decomposition by clique separators
- Safe separators for treewidth
- Triangulated graphs and the elimination process
Cited in
(26)- Decomposition by clique separators
- Computing a clique tree with the algorithm maximal label search
- Excluding hooks and their complements
- On the complexity of computing treebreadth
- Trees of tangles in abstract separation systems
- Evaluating Datalog via tree automata and cycluits
- Efficiently decomposing, recognizing and triangulating hole-free graphs without diamonds
- Characterizing atoms that result from decomposition by clique separators
- Optimal decomposition by clique separators
- Applying clique-decomposition for computing Gromov hyperbolicity
- Finding a maximum minimal separator: graph classes and fixed-parameter tractability
- Graphs with polynomially many minimal separators
- Completion to chordal distance-hereditary graphs: a quartic vertex-kernel
- On the complexity of computing treebreadth
- On computing the Gromov hyperbolicity
- A decomposition theorem for chordal graphs and its applications
- Fixed-Parameter Tractable Canonization and Isomorphism Test for Graphs of Bounded Treewidth
- Organizing the atoms of the clique separator decomposition into an atom tree
- Clique separator decomposition of hole-free and diamond-free graphs and algorithmic consequences
- Revisiting decomposition by clique separators
- Decomposition by maxclique separators
- The clique minimal separator decomposition of a hypergraph
- Inapproximability results related to monophonic convexity
- The G-Wishart Weighted Proposal Algorithm: Efficient Posterior Computation for Gaussian Graphical Models
- Thick forests
- The maximum infection time in the geodesic and monophonic convexities
This page was built for publication: An introduction to clique minimal separator decomposition
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1662549)
