Triangulation and clique separator decomposition of claw-free graphs

DOI10.1007/978-3-642-34611-8_5MaRDI QIDQ5200490zbMATH OpenOpenAlexFDO

Authors Anne Berry, Annegret K. Wagler

Publication date 6 November 2012

Published in Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-34611-8_5

zbMATH Keywords

claw-free graphminimal triangulationclique separator decomposition

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms (68W40) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• Revisiting decomposition by clique separators
• Recognition and computation of minimal triangulations for AT-free claw-free and co-comparability graphs
• scientific article; zbMATH DE number 1305094
• Computing Minimal Triangulations in Time O(nalpha log n) = o(n2.376)
• Computing minimal triangulations in time \(O(n^{\alpha \log n}) = o(n^{2.376})\)

Cited in

(13)

• Organizing the atoms of the clique separator decomposition into an atom tree
• Efficiently decomposing, recognizing and triangulating hole-free graphs without diamonds
• scientific article; zbMATH DE number 7080199 (Why is no real title available?)
• On claw-free asteroidal triple-free graphs
• Graphs with at most two moplexes
• Revisiting decomposition by clique separators
• Computing a clique tree with the algorithm maximal label search
• scientific article; zbMATH DE number 5304940 (Why is no real title available?)
• Disjoint cliques in claw-free graphs
• Decomposition of a Complete Multi-Partite Graph into Isomorphic Claws
• scientific article; zbMATH DE number 7204318 (Why is no real title available?)
• Claw-free graphs. IV: Decomposition theorem
• On the d-claw vertex deletion problem

This page was built for publication: Triangulation and clique separator decomposition of claw-free graphs

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