An introduction to clique minimal separator decomposition

DOI10.3390/A3020197zbMATH Open1461.05161OpenAlexW2072082202MaRDI QIDQ1662549FDOQ1662549

Authors Anne Berry, Romain Pogorelcnik, Geneviève Simonet 

Publication date 20 August 2018

Published in Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.3390/a3020197

zbMATH Keywords

graph decompositionminimal triangulationclique minimal separator

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• Optimal decomposition by clique separators
• Publication:4944975
• Decomposition by clique separators
• Decomposition by maxclique separators
• Revisiting decomposition by clique separators

Cites work

• scientific article; zbMATH DE number 432771 (Why is no real title available?)
• scientific article; zbMATH DE number 554762 (Why is no real title available?)
• 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
• 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

(24)

• Decomposition by maxclique separators
• Efficiently decomposing, recognizing and triangulating hole-free graphs without diamonds
• Computing a clique tree with the algorithm maximal label search
• Characterizing atoms that result from decomposition by clique separators
• Fixed-Parameter Tractable Canonization and Isomorphism Test for Graphs of Bounded Treewidth
• Graphs with polynomially many minimal separators
• Finding a maximum minimal separator: graph classes and fixed-parameter tractability
• Revisiting decomposition by clique separators
• On computing the Gromov hyperbolicity
• On the complexity of computing treebreadth
• On the complexity of computing treebreadth
• The clique minimal separator decomposition of a hypergraph
• Decomposition by clique separators
• Organizing the atoms of the clique separator decomposition into an atom tree
• A decomposition theorem for chordal graphs and its applications
• Applying clique-decomposition for computing Gromov hyperbolicity
• The G-Wishart Weighted Proposal Algorithm: Efficient Posterior Computation for Gaussian Graphical Models
• Trees of tangles in abstract separation systems
• The maximum infection time in the geodesic and monophonic convexities
• Excluding hooks and their complements
• Evaluating Datalog via tree automata and cycluits
• Clique separator decomposition of hole-free and diamond-free graphs and algorithmic consequences
• Completion to chordal distance-hereditary graphs: a quartic vertex-kernel
• Inapproximability results related to monophonic convexity

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)