Cograph editing: complexity and parameterized algorithms

DOI10.1007/978-3-642-22685-4_10MaRDI QIDQ3087943zbMATH OpenOpenAlexFDO

Authors Yunlong Liu, Jianxin Wang, Jiong Guo, Jianer Chen

Publication date 17 August 2011

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-22685-4_10

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Complexity and parameterized algorithms for cograph editing
• Faster algorithms for cograph edge modification problems
• Cograph editing: Merging modules is equivalent to editing P₄s
• Alternative parameterizations for cluster editing
• A golden ratio parameterized algorithm for cluster editing

Cited in

(13)

• Orthology relations, symbolic ultrametrics, and cographs
• On the (non-)existence of polynomial kernels for \(P _{l }\)-free edge modification problems
• Faster algorithms for cograph edge modification problems
• Chordal editing is fixed-parameter tractable
• On symbolic ultrametrics, cotree representations, and cograph edge decompositions and partitions
• Cograph editing: Merging modules is equivalent to editing P₄s
• Orthology relation and gene tree correction: complexity results
• Fast FPT-Algorithms for Cleaning Grids
• A quasi-quadratic vertex-kernel for cograph edge editing
• Complexity and parameterized algorithms for cograph editing
• Parameterized reductions and algorithms for a graph editing problem that generalizes vertex cover
• On tree representations of relations and graphs: symbolic ultrametrics and cograph edge decompositions
• Spiders can be recognized by counting their legs

This page was built for publication: Cograph editing: complexity and parameterized algorithms

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