Complexity of the cluster deletion problem on subclasses of chordal graphs
DOI10.1016/J.TCS.2015.07.001zbMATH Open1330.05122OpenAlexW846902610MaRDI QIDQ496003FDOQ496003
Mario Valencia-Pabon, Guillermo Durán, 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
Recommendations
interval graphsNP-completenesschordal graphscographssplit graphsblock graphscliquessubmodular functionscluster deletionedge deletion
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)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Correlation clustering
- Cluster editing with locally bounded modifications
- Cluster analysis and mathematical programming
- Title not available (Why is that?)
- Maximum matching and a polyhedron with 0,1-vertices
- Title not available (Why is that?)
- A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
- A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions
- Title not available (Why is that?)
- Correlation clustering in general weighted graphs
- Cluster graph modification problems
- Editing Simple Graphs
- Even faster parameterized cluster deletion and cluster editing
- ON THE APPROXIMABILITY OF MAXIMUM AND MINIMUM EDGE CLIQUE PARTITION PROBLEMS
- The cluster deletion problem for cographs
- Cluster editing problem for points on the real line: a polynomial time algorithm
- 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
- On the Clique Editing Problem
Cited In (10)
- Title not available (Why is that?)
- Strong triadic closure in cographs and graphs of low maximum degree
- Title not available (Why is that?)
- On the parameterized complexity of s-club cluster deletion problems
- Cluster deletion on interval graphs and split related graphs
- Maximizing the strong triadic closure in split graphs and proper interval graphs
- Structural parameterization of cluster deletion
- Vertex deletion on split graphs: beyond 4-hitting set
- A new approximate cluster deletion algorithm for diamond-free graphs
- Subtraction-free complexity, cluster transformations, and spanning trees
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)
