Complexity and parameterized algorithms for cograph editing

DOI10.1016/j.tcs.2011.11.040zbMath1253.68179OpenAlexW2008978934WikidataQ56475005 ScholiaQ56475005MaRDI QIDQ690461

Jiong Guo, Jianxin Wang, Yunlong Liu, Jian'er Chen

Publication date: 27 November 2012

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2011.11.040

zbMATH Keywords

NP-hardnessparameterized algorithms\(P_{4}\)-sparse graphcograph editing

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (20)

Linear-time minimal cograph editing ⋮ Parameterizing edge modification problems above lower bounds ⋮ On Symbolic Ultrametrics, Cotree Representations, and Cograph Edge Decompositions and Partitions ⋮ Complete characterization of incorrect orthology assignments in best match graphs ⋮ Complexity of modification problems for best match graphs ⋮ A survey of parameterized algorithms and the complexity of edge modification ⋮ Resolving prime modules: the structure of pseudo-cographs and galled-tree explainable graphs ⋮ Spiders can be recognized by counting their legs ⋮ Cograph editing: Merging modules is equivalent to editing P_4s ⋮ Improved kernel results for some FPT problems based on simple observations ⋮ Edge deletion problems: branching facilitated by modular decomposition ⋮ Faster and enhanced inclusion-minimal cograph completion ⋮ On tree representations of relations and graphs: symbolic ultrametrics and cograph edge decompositions ⋮ Complexity of modification problems for reciprocal best match graphs ⋮ A polynomial kernel for trivially perfect editing ⋮ On the threshold of intractability ⋮ Best match graphs and reconciliation of gene trees with species trees ⋮ Defining and identifying cograph communities in complex networks ⋮ Faster algorithms for cograph edge modification problems ⋮ An effective branching strategy based on structural relationship among multiple forbidden induced subgraphs

Cites Work

• A survey of the algorithmic aspects of modular decomposition
• Graph-modeled data clustering: Exact algorithms for clique generation
• A tree representation for \(P_ 4\)-sparse graphs
• Modular decomposition and transitive orientation
• Fixed-parameter tractability of graph modification problems for hereditary properties
• A general method to speed up fixed-parameter-tractable algorithms
• Automated generation of search tree algorithms for hard graphs modification problems
• Applying modular decomposition to parameterized cluster editing problems
• NP-completeness results for edge modification problems
• On a property of the class of n-colorable graphs
• On the (Non-)existence of Polynomial Kernels for P l -free Edge Modification Problems
• A Novel Branching Strategy for Parameterized Graph Modification Problems
• Improved Algorithms for Bicluster Editing
• A 2k Kernel for the Cluster Editing Problem
• A Linear Recognition Algorithm for Cographs
• The complexity of some edge deletion problems
• Recognizing $P_4 $-Sparse Graphs in Linear Time
• Complexity classification of some edge modification problems

This page was built for publication: Complexity and parameterized algorithms for cograph editing