Complexity of the cluster deletion problem on subclasses of chordal graphs

DOI10.1016/j.tcs.2015.07.001zbMath1330.05122OpenAlexW846902610MaRDI QIDQ496003

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

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

NP-completenesscliqueschordal graphscographssplit graphsblock graphsinterval graphssubmodular functionscluster deletionedge deletion

Mathematics Subject Classification ID

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

Related Items

Structural parameterization of cluster deletion, Maximizing the strong triadic closure in split graphs and proper interval graphs, Strong triadic closure in cographs and graphs of low maximum degree, Unnamed Item, Cluster deletion on interval graphs and split related graphs, A new approximate cluster deletion algorithm for diamond-free graphs, Vertex deletion on split graphs: beyond 4-hitting set, Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The cluster deletion problem for cographs
• Correlation clustering
• Cluster editing with locally bounded modifications
• Cluster analysis and mathematical programming
• Cluster editing problem for points on the real line: a polynomial time algorithm
• A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
• Cluster graph modification problems
• Even faster parameterized cluster deletion and cluster editing
• 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
• Correlation clustering in general weighted graphs
• On the Clique Editing Problem
• Editing Simple Graphs
• A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions
• ON THE APPROXIMABILITY OF MAXIMUM AND MINIMUM EDGE CLIQUE PARTITION PROBLEMS
• Maximum matching and a polyhedron with 0,1-vertices