Article ID: | iaor20118130 |
Volume: | 61 |
Issue: | 2 |
Start Page Number: | 252 |
End Page Number: | 273 |
Publication Date: | Oct 2011 |
Journal: | Algorithmica |
Authors: | Kratochvl Jan, Kratsch Dieter, Liedloff Mathieu, Fomin V, Golovach A |
Keywords: | branching process |
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