The cluster deletion problem for cographs
DOI10.1016/J.DISC.2013.08.017zbMATH Open1280.05099OpenAlexW2072445778MaRDI QIDQ394219FDOQ394219
Authors: Yong Gao, Donovan R. Hare, James Nastos 
Publication date: 24 January 2014
Published in: Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.disc.2013.08.017
Recommendations
fixed-parameter tractabilityinteger partitionscographscliquesgraph modificationcluster 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) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Cites Work
- Fixed-parameter tractability of graph modification problems for hereditary properties
- Graph Classes: A Survey
- Correlation clustering
- Cluster editing with locally bounded modifications
- The ellipsoid method and its consequences in combinatorial optimization
- Independent sets in extensions of 2\(K_{2}\)-free graphs
- Algorithmic graph theory and perfect graphs
- The intersection graphs of subtrees in trees are exactly the chordal graphs
- Title not available (Why is that?)
- Title not available (Why is that?)
- A Linear Recognition Algorithm for Cographs
- Four classes of perfectly orderable graphs
- Cluster graph modification problems
- Even faster parameterized cluster deletion and cluster editing
- Improved algorithms for weakly chordal graphs
- A novel branching strategy for parameterized graph modification problems
- ON THE APPROXIMABILITY OF MAXIMUM AND MINIMUM EDGE CLIQUE PARTITION PROBLEMS
- Bounded-degree techniques accelerate some parameterized graph algorithms
- Title not available (Why is that?)
Cited In (17)
- Cograph editing: Merging modules is equivalent to editing P_4s
- 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
- Strong triadic closure in cographs and graphs of low maximum degree
- Cluster deletion revisited
- Faster algorithms for cograph edge modification problems
- On the parameterized complexity of s-club cluster deletion problems
- A polynomial-time algorithm for cluster deletion on (diamond, Butterfly)-free graphs
- Resolving prime modules: the structure of pseudo-cographs and galled-tree explainable graphs
- Cluster deletion on interval graphs and split related graphs
- Cluster deletion on interval graphs and split related graphs
- Structural parameterization of cluster deletion
- Indirect identification of horizontal gene transfer
- Defining and identifying cograph communities in complex networks
- From modular decomposition trees to level-1 networks: pseudo-cographs, polar-cats and prime polar-cats
- A new approximate cluster deletion algorithm for diamond-free graphs
- Complexity of the cluster deletion problem on subclasses of chordal graphs
- On the \(d\)-claw vertex deletion problem
This page was built for publication: The cluster deletion problem for cographs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q394219)
