Capacitated power dominating set problem: a solution approach based on forbidden propagation sets
Mauro Lucci, Diego Delle Donne, Mariana Escalante · 2026
Read Capacitated power dominating set problem: a solution approach based on forbidden propagation sets by Mauro Lucci, Diego Delle Donne, Mariana Escalante (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-18533.txt.
Description
Mauro Lucci and two co-authors offer, in a 2026 paper, forbidden propagation sets for the capacitated power dominating set problem. These are patterns that cannot co-occur in any feasible solution. The idea yields a new class of integer linear programs mixing infection-based variables with exponentially many constraints, without big-M constraints. Structural traits, valid inequalities, redundancy-breaking rules, and a lazy-separation routine based on cycle detection follow. Tests on benchmarks up to 14,000 vertices show 1.7-fold faster runs than adapted existing methods.
Catalog record
| CREATOR | Mauro Lucci, Diego Delle Donne, Mariana Escalante |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 77760 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.18533