Complexity of the cluster deletion problem on subclasses of chordal graphs

DOI10.1016/J.TCS.2015.07.001MaRDI QIDQ496003zbMATHOpenAlexFDO

Authors Guillermo Durán, Mario Valencia-Pabon, Flavia Bonomo

Publication date 16 September 2015

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2015.07.001

zbMATH Keywords

interval graphsNP-completenesschordal graphscographssplit graphsblock graphscliquessubmodular functionscluster deletionedge deletion

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Signed and weighted graphs (05C22) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• Cluster deletion on interval graphs and split related graphs
• The cluster deletion problem for cographs
• A polynomial-time algorithm for cluster deletion on (diamond, Butterfly)-free graphs
• Cluster graph modification problems
• scientific article; zbMATH DE number 1953109

Cites work

• scientific article; zbMATH DE number 3579840 (Why is no real title available?)
• scientific article; zbMATH DE number 3632548 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 554762 (Why is no real title available?)
• scientific article; zbMATH DE number 3307330 (Why is no real title available?)
• A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
• A one-to-one correspondence between potential solutions of the cluster deletion problem and the minimum sum coloring problem, and its application to \(P_4\)-sparse graphs
• Cluster analysis and mathematical programming
• Cluster editing problem for points on the real line: a polynomial time algorithm
• Cluster editing with locally bounded modifications
• Cluster graph modification problems
• Correlation clustering
• Correlation clustering in general weighted graphs
• Editing simple graphs
• Even faster parameterized cluster deletion and cluster editing
• Maximum matching and a polyhedron with 0,1-vertices
• ON THE APPROXIMABILITY OF MAXIMUM AND MINIMUM EDGE CLIQUE PARTITION PROBLEMS
• On the clique editing problem
• The cluster deletion problem for cographs

Cited in

(15)

• On the parameterized complexity of s-club cluster deletion problems
• The Computational Complexity of the ChordLink Model
• The cluster deletion problem for cographs
• Cluster deletion on interval graphs and split related graphs
• Cluster deletion on interval graphs and split related graphs
• Subtraction-free complexity, cluster transformations, and spanning trees
• Complexity of the (Connected) Cluster Vertex Deletion Problem on H-free Graphs
• \(s\)-club cluster vertex deletion on interval and well-partitioned chordal graphs
• Maximizing the strong triadic closure in split graphs and proper interval graphs
• Maximizing the strong triadic closure in split graphs and proper interval graphs
• Strong triadic closure in cographs and graphs of low maximum degree
• A polynomial-time algorithm for cluster deletion on (diamond, Butterfly)-free graphs
• A new approximate cluster deletion algorithm for diamond-free graphs
• Vertex deletion on split graphs: beyond 4-hitting set
• Structural parameterization of cluster deletion

This page was built for publication: Complexity of the cluster deletion problem on subclasses of chordal graphs

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