An Effective Branching Strategy for Some Parameterized Edge Modification Problems with Multiple Forbidden Induced Subgraphs Conference Paper uri icon

abstract

  • Branching on forbidden induced subgraphs is a genetic strategy to obtain parameterized algorithms for many edge modification problems. For such a problem in which the graph property is defined by multiple forbidden induced subgraphs, branching process is trivially performed on each subgraph. Thus, the size of the resulting search tree is dominated by the size of the largest forbidden subgraph. In this paper, we present a simple strategy for deriving significantly improved branching rules for dealing with multiple forbidden subgraphs by edge modifications. The basic idea hereby is that while constructing branching rules for the largest forbidden subgraph, we sufficiently take into account the structural relationship between it and other forbidden subgraphs. By applying this strategy, we obtain improved parameterized algorithms for edge modification problems for several graph properties such as proper interval, 3-leaf power, threshold and co-trivially perfect graphs. 2013 Springer-Verlag Berlin Heidelberg.

name of conference

  • Computing and Combinatorics, 19th International Conference, COCOON 2013, Hangzhou, China, June 21-23, 2013. Proceedings

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., Xu, C., Guo, J., & Chen, J.

citation count

  • 1

complete list of authors

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

publication date

  • October 2013