An introduction to clique minimal separator decomposition
From MaRDI portal
Publication:1662549
DOI10.3390/a3020197zbMath1461.05161OpenAlexW2072082202MaRDI QIDQ1662549
Romain Pogorelcnik, Geneviève Simonet, Anne Berry
Publication date: 20 August 2018
Published in: Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.3390/a3020197
Extremal problems in graph theory (05C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Related Items (20)
Characterizing atoms that result from decomposition by clique separators ⋮ The G-Wishart Weighted Proposal Algorithm: Efficient Posterior Computation for Gaussian Graphical Models ⋮ Applying clique-decomposition for computing Gromov hyperbolicity ⋮ Computing a clique tree with the algorithm maximal label search ⋮ Finding a maximum minimal separator: graph classes and fixed-parameter tractability ⋮ Excluding hooks and their complements ⋮ Graphs with polynomially many minimal separators ⋮ Completion to chordal distance-hereditary graphs: a quartic vertex-kernel ⋮ Organizing the atoms of the clique separator decomposition into an atom tree ⋮ The maximum infection time in the geodesic and monophonic convexities ⋮ Fixed-Parameter Tractable Canonization and Isomorphism Test for Graphs of Bounded Treewidth ⋮ Revisiting Decomposition by Clique Separators ⋮ Decomposition by maxclique separators ⋮ Trees of tangles in abstract separation systems ⋮ Inapproximability results related to monophonic convexity ⋮ On the complexity of computing treebreadth ⋮ On the Complexity of Computing Treebreadth ⋮ On Computing the Gromov Hyperbolicity ⋮ Evaluating Datalog via tree automata and cycluits ⋮ Efficiently decomposing, recognizing and triangulating hole-free graphs without diamonds
Cites Work
- Unnamed Item
- Unnamed Item
- On rigid circuit graphs
- Minimal triangulations of graphs: a survey
- A vertex incremental approach for maintaining chordality
- Safe separators for treewidth
- Minimal fill in O(\(n^{2.69}\)) time
- Decomposition by clique separators
- An algorithm for finding clique cut-sets
- Algorithms on clique separable graphs
- Maximum cardinality search for computing minimal triangulations of graphs
- Optimal decomposition by clique separators
- On clique separators, nearly chordal graphs, and the Maximum Weight Stable Set Problem
- Triangulated graphs and the elimination process
- Computing the Minimum Fill-In is NP-Complete
- Algorithmic Aspects of Vertex Elimination on Graphs
- Maximal Label Search Algorithms to Compute Perfect and Minimal Elimination Orderings
- A wide-range algorithm for minimal triangulation from an arbitrary ordering
- Computing Minimal Triangulations in Time O(nalpha log n) = o(n2.376)
This page was built for publication: An introduction to clique minimal separator decomposition
