Branch and recharge: exact algorithms for generalized domination (Q639293): Difference between revisions

The authors present a new approach to the design and analysis of branching algorithms for exact solutions of NP-hard problems. The approach of branch and recharge is based on the combination of a branching algorithm and a recharging mechanism. The new methodology is illustrated using a generalization of the domination problem on graphs, \((\sigma,\varrho)\)-domination. A vertex subset \(S\subseteq V(G)\) is called a \((\sigma,\varrho)\)-dominating set if \(|N(v)\cap S|\in \sigma\) for all \(v\in S\) and \(|N(v)\cap S|\in \varrho\) for all \(v\in V\backslash S\), where \(\sigma\) and \(\varrho\) are nonempty sets of integers. The paper presents an algorithm with time complexity \(O^*(c^n)\) for the enumeration of all \((\sigma,\varrho)\)-dominating sets, where the constant \(c<2\) depends on \(\sigma\) and \(\varrho\).