Paper Info
Title
Inclusion/Exclusion Branching For Partial Dominating Set And Set Splitting
Abstract
Inclusion/exclusion branching is a way to branch on requirements imposed on problems, in contrast to the classical branching on parts of the solution. The technique turned out to be useful for finding and counting (minimum) dominating sets (van Rooij et al., ESA 2009). In this paper, we extend the technique to the setting where one is given a set of properties and seeks (or wants to count) solutions that have at least a given number of these properties. Using this extension, we obtain new algorithms for PARTIAL DOMINATING SET and the parameterised problem k-SET SPLITTING. In particular, we apply the new idea to the fastest polynomial space algorithm for counting dominating sets, and directly obtain a polynomial space algorithm for PARTIAL DOMINATING SET with the same running time (up to a linear factor). Combining the new idea with some previous work, we also give a polynomial space algorithm for k-SET SPLITTING that improves the fastest known result significantly.
Year
DOI
Venue
2010
10.1007/978-3-642-17493-3_20
PARAMETERIZED AND EXACT COMPUTATION
Keywords
Field
DocType
dominating set
Combinatorics,Dominating set,Steiner tree problem,PSPACE,Mathematics,Branching (version control)
Conference
Volume
ISSN
Citations 
6478
0302-9743
6
PageRank 
References 
Authors
0.53
23
2
Name
Order
Citations
PageRank
Jesper Nederlof129424.22
Johan M. M. van Rooij219211.20