The cluster deletion problem for cographs

DOI10.1016/J.DISC.2013.08.017MaRDI QIDQ394219zbMATHOpenAlexFDO

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

zbMATH Keywords

fixed-parameter tractabilityinteger partitionscographscliquesgraph modificationcluster 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) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• Cluster deletion revisited
• Cluster deletion on interval graphs and split related graphs
• Complexity of the cluster deletion problem on subclasses of chordal graphs
• A polynomial-time algorithm for cluster deletion on (diamond, Butterfly)-free graphs
• Cluster graph modification problems

Cites work

• scientific article; zbMATH DE number 1375569 (Why is no real title available?)
• scientific article; zbMATH DE number 2011849 (Why is no real title available?)
• scientific article; zbMATH DE number 3445275 (Why is no real title available?)
• A Linear Recognition Algorithm for Cographs
• A novel branching strategy for parameterized graph modification problems
• Algorithmic graph theory and perfect graphs
• Bounded-degree techniques accelerate some parameterized graph algorithms
• Cluster editing with locally bounded modifications
• Cluster graph modification problems
• Correlation clustering
• Even faster parameterized cluster deletion and cluster editing
• Fixed-parameter tractability of graph modification problems for hereditary properties
• Four classes of perfectly orderable graphs
• Graph Classes: A Survey
• Improved algorithms for weakly chordal graphs
• Independent sets in extensions of 2\(K_{2}\)-free graphs
• ON THE APPROXIMABILITY OF MAXIMUM AND MINIMUM EDGE CLIQUE PARTITION PROBLEMS
• The ellipsoid method and its consequences in combinatorial optimization
• The intersection graphs of subtrees in trees are exactly the chordal graphs

Cited in

(17)

• On the parameterized complexity of s-club cluster deletion problems
• Cluster deletion revisited
• Complexity of the cluster deletion problem on subclasses of chordal graphs
• 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
• Indirect identification of horizontal gene transfer
• 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
• Cograph editing: Merging modules is equivalent to editing P_4s
• Defining and identifying cograph communities in complex networks
• From modular decomposition trees to level-1 networks: pseudo-cographs, polar-cats and prime polar-cats
• Strong triadic closure in cographs and graphs of low maximum degree
• Faster algorithms for cograph edge modification problems
• A polynomial-time algorithm for cluster deletion on (diamond, Butterfly)-free graphs
• A new approximate cluster deletion algorithm for diamond-free graphs
• On the \(d\)-claw vertex deletion problem
• Structural parameterization of cluster deletion

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)