Cograph Editing: Complexity and Parameterized Algorithms Conference Paper

abstract

• Cograph Editing is to find for a given graph G = (V,E) a set of at most k edge additions and deletions that transform G into a cograph. The computational complexity of this problem was open in the past. In this paper, we show that this problem is NP-hard, and present a parameterized algorithm based on a refined search tree technique with a running time of O(4.612k + |V|4.5)), which improves the trivial algorithm of running time O(6k + |V|4.5). 2011 Springer-Verlag.

name of conference

• Computing and Combinatorics - 17th Annual International Conference, COCOON 2011, Dallas, TX, USA, August 14-16, 2011. Proceedings

authors

• Chen, Jianer

published proceedings

• Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

author list (cited authors)

• Liu, Y., Wang, J., Guo, J., & Chen, J.

citation count

• 11

complete list of authors

• Liu, Yunlong||Wang, Jianxin||Guo, Jiong||Chen, Jianer

publication date

• August 2011

publisher

• Springer Nature  Publisher

published in

• Lecture Notes in Computer Science  Journal

keywords

• 46 Information And Computing Sciences
• Bioengineering

Digital Object Identifier (DOI)

• 10.1007/978-3-642-22685-4_10

International Standard Book Number (ISBN) 13

• 9783642226847

start page

• 110

end page

• 121

volume

• 6842

URL

• http%3A%2F%2Fdx.doi.org%2F10.1007%2F978-3-642-22685-4_10