Anzeige
Erschienen in:
2010 | OriginalPaper | Buchkapitel
Inclusion/Exclusion Branching for Partial Dominating Set and Set Splitting
verfasst von : Jesper Nederlof, Johan M. M. van Rooij
Erschienen in: Parameterized and Exact Computation
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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.