Branch and Recharge: Exact Algorithms for Generalized Domination

Branch and Recharge: Exact Algorithms for Generalized Domination

0.00 Avg rating0 Votes
Article ID: iaor20118130
Volume: 61
Issue: 2
Start Page Number: 252
End Page Number: 273
Publication Date: Oct 2011
Journal: Algorithmica
Authors: , , , ,
Keywords: branching process
Abstract:

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 SV of an undirected graph G=(V(G),E(G)) is called a (σ,ρ)‐dominating set of G if |N(v)∩S|∈σ for all vS and |N(v)∩S|∈ρ for all vV\S. This notion generalizes many domination‐type graph invariants.

Reviews

Required fields are marked *. Your email address will not be published.