Complexity and parameterized algorithms for cograph editing

DOI10.1016/J.TCS.2011.11.040MaRDI QIDQ690461zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Yunlong Liu, Jianxin Wang, Jiong Guo, Jianer 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)

Recommendations

• Cograph editing: complexity and parameterized algorithms
• Faster algorithms for cograph edge modification problems
• Cograph editing: Merging modules is equivalent to editing P_4s
• On the clique editing problem
• Alternative parameterizations for cluster editing

Cites work

• A Linear Recognition Algorithm for Cographs
• A \(2k\) kernel for the cluster editing problem
• A general method to speed up fixed-parameter-tractable algorithms
• A novel branching strategy for parameterized graph modification problems
• A survey of the algorithmic aspects of modular decomposition
• A tree representation for \(P_ 4\)-sparse graphs
• Applying modular decomposition to parameterized cluster editing problems
• Automated generation of search tree algorithms for hard graphs modification problems
• Complexity classification of some edge modification problems
• Fixed-parameter tractability of graph modification problems for hereditary properties
• Graph-modeled data clustering: Exact algorithms for clique generation
• Improved Algorithms for Bicluster Editing
• Modular decomposition and transitive orientation
• 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
• Recognizing $P_4 $-Sparse Graphs in Linear Time
• The complexity of some edge deletion problems

Cited in

(20)

• Cograph editing: Merging modules is equivalent to editing P_4s
• Edge deletion problems: branching facilitated by modular decomposition
• Faster algorithms for cograph edge modification problems
• On tree representations of relations and graphs: symbolic ultrametrics and cograph edge decompositions
• Best match graphs and reconciliation of gene trees with species trees
• An effective branching strategy based on structural relationship among multiple forbidden induced subgraphs
• A faster parameterized algorithm for bipartite 1-sided vertex explosion
• A quasi-quadratic vertex-kernel for cograph edge editing
• A survey of parameterized algorithms and the complexity of edge modification
• Resolving prime modules: the structure of pseudo-cographs and galled-tree explainable graphs
• Complete characterization of incorrect orthology assignments in best match graphs
• Cograph editing: complexity and parameterized algorithms
• On symbolic ultrametrics, cotree representations, and cograph edge decompositions and partitions
• Defining and identifying cograph communities in complex networks
• Complexity of modification problems for reciprocal best match graphs
• Spiders can be recognized by counting their legs
• Parameterized reductions and algorithms for a graph editing problem that generalizes vertex cover
• Complexity of modification problems for best match graphs
• Improved kernel results for some FPT problems based on simple observations
• Linear-time minimal cograph editing

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q690461)