An effective branching strategy based on structural relationship among multiple forbidden induced subgraphs

Yunlong Liu (), Jianxin Wang (), Chao Xu, Jiong Guo () and Jianer Chen ()
Additional contact information
Yunlong Liu: Central South University
Jianxin Wang: Central South University
Chao Xu: Central South University
Jiong Guo: Universität des Saarlandes
Jianer Chen: Central South University

Journal of Combinatorial Optimization, 2015, vol. 29, issue 1, No 17, 257-275

Abstract: 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 to deal 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 3-leaf power, proper interval, threshold and co-trivially perfect graphs.

Keywords: Branching strategy; Edge modification; Multiple forbidden induced subgraph (search for similar items in EconPapers)
Date: 2015
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-014-9733-1 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:29:y:2015:i:1:d:10.1007_s10878-014-9733-1

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-014-9733-1

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().