caa a22 4500 445805528 CHVBK 20180317145155.0 cr unu---uuuuu 170323e20111001xx s 000 0 eng 10.1007/s00453-010-9418-9 doi (NATIONALLICENCE)springer-10.1007/s00453-010-9418-9 Branch and Recharge: Exact Algorithms forGeneralized Domination [Elektronische Daten] [Fedor Fomin, Petr Golovach, Jan Kratochvíl, Dieter Kratsch, Mathieu Liedloff] In this paper we present branching algorithms for infinite classes of problems. The novelty in the design and analysis of our branching algorithms lies in the fact that the weights are redistributed over the graph by the algorithms. Our particular setting to make this idea work is a combination of a branching approach with a recharging mechanism. We call it Branch & Recharge. To demonstrate this approach we consider a generalized domination problem. Let σ and ϱ be two nonempty sets of nonnegative integers. A vertex subset S⊆V of an undirected graph G=(V(G),E(G)) is called a (σ,ϱ)-dominating set of G if |N(v)∩S|∈σ for all v∈S and |N(v)∩S|∈ϱ for all v∈V∖S. This notion generalizes many domination-type graph invariants. We present Branch & Recharge algorithms enumerating all (σ,ϱ)-dominating sets of an input graph G in time O *(c n) for some c<2, if σ is successor-free, i.e., it does not contain two consecutive integers, and either both σ and ϱ are finite, or one of them is finite and σ∩ϱ=∅. Our algorithm implies a non trivial upper bound of O *(c n) on the number of (σ,ϱ)-dominating sets in an n-vertex graph under the above conditions on σ and ϱ. Springer Science+Business Media, LLC, 2010 Exact exponential algorithms nationallicence NP-hard problems nationallicence Generalized domination nationallicence Branch and recharge nationallicence Fomin Fedor Department of Informatics, University of Bergen, 5020, Bergen, Norway aut Golovach Petr School of Engineering and Computing Sciences, Durham University, South Road, DH1 3LE, Durham, UK aut Kratochvíl Jan Department of Applied Mathematics, and Institute for Theoretical Computer Science, Charles University, Malostranské nám. 25, 118 00, Praha 1, Czech Republic aut Kratsch Dieter Laboratoire d'Informatique Théorique et Appliquée, Université Paul Verlaine—Metz, 57045, Metz Cedex 01, France aut Liedloff Mathieu Laboratoire d'Informatique Fondamentale d'Orléans, Université d'Orléans, 45067, Orléans Cedex 2, France aut Algorithmica Springer-Verlag 61/2(2011-10-01), 252-273 0178-4617 61:2<252 2011 61 453 https://doi.org/10.1007/s00453-010-9418-9 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00453-010-9418-9 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Fomin Fedor Department of Informatics, University of Bergen, 5020, Bergen, Norway aut NATIONALLICENCE 700 1- Golovach Petr School of Engineering and Computing Sciences, Durham University, South Road, DH1 3LE, Durham, UK aut NATIONALLICENCE 700 1- Kratochvíl Jan Department of Applied Mathematics, and Institute for Theoretical Computer Science, Charles University, Malostranské nám. 25, 118 00, Praha 1, Czech Republic aut NATIONALLICENCE 700 1- Kratsch Dieter Laboratoire d'Informatique Théorique et Appliquée, Université Paul Verlaine—Metz, 57045, Metz Cedex 01, France aut NATIONALLICENCE 700 1- Liedloff Mathieu Laboratoire d'Informatique Fondamentale d'Orléans, Université d'Orléans, 45067, Orléans Cedex 2, France aut NATIONALLICENCE 773 0- Algorithmica Springer-Verlag 61/2(2011-10-01), 252-273 0178-4617 61:2<252 2011 61 453 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer