The cluster deletion problem for cographs

DOI10.1016/j.disc.2013.08.017zbMath1280.05099OpenAlexW2072445778MaRDI QIDQ394219

Donovan R. Hare, James Nastos, Yong Gao

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

cliquescographsinteger partitionsfixed-parameter tractabilitygraph modificationcluster 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)

Related Items

From modular decomposition trees to level-1 networks: pseudo-cographs, polar-cats and prime polar-cats, Structural parameterization of cluster deletion, Resolving prime modules: the structure of pseudo-cographs and galled-tree explainable graphs, Cograph editing: Merging modules is equivalent to editing P_4s, Complexity of the cluster deletion problem on subclasses of chordal graphs, On the relation of strong triadic closure and cluster deletion, Strong triadic closure in cographs and graphs of low maximum degree, Unnamed Item, Cluster deletion on interval graphs and split related graphs, Indirect identification of horizontal gene transfer, A new approximate cluster deletion algorithm for diamond-free graphs, Defining and identifying cograph communities in complex networks, 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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Correlation clustering
• Cluster editing with locally bounded modifications
• The ellipsoid method and its consequences in combinatorial optimization
• Fixed-parameter tractability of graph modification problems for hereditary properties
• Independent sets in extensions of 2\(K_{2}\)-free graphs
• Cluster graph modification problems
• Algorithmic graph theory and perfect graphs
• Even faster parameterized cluster deletion and cluster editing
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• 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
• A Linear Recognition Algorithm for Cographs
• Four classes of perfectly orderable graphs
• Graph Classes: A Survey