An Integer Programming Approach for Fault-Tolerant Connected Dominating Sets

DOI10.1287/ijoc.2014.0619zbMath1327.90348OpenAlexW2007101062MaRDI QIDQ2942693

Austin Buchanan, Je Sang Sung, Eduardo L. Pasiliao, Sergiy I. Butenko

Publication date: 11 September 2015

Published in: INFORMS Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/6819de12d0d0bc76745cb90fab4a070bcc3b27a0

zbMATH Keywords

integer programmingconnected dominating setfault-tolerant\(k\)-connected \(m\)-dominating set

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Integer programming (90C10)

Related Items (16)

A new branch-and-cut approach for the generalized regenerator location problem ⋮ Computational approaches for zero forcing and related problems ⋮ Spanning trees with a constraint on the number of leaves. A new formulation ⋮ Imposing Contiguity Constraints in Political Districting Models ⋮ A heuristic approach for dividing graphs into bi-connected components with a size constraint ⋮ A Fast Vertex Weighting-Based Local Search for Finding Minimum Connected Dominating Sets ⋮ Solving the Distance-Based Critical Node Problem ⋮ On imposing connectivity constraints in integer programs ⋮ Optimal connected subgraphs: Integer programming formulations and polyhedra ⋮ Extended formulations for perfect domination problems and their algorithmic implications ⋮ Breaking the O(ln n) Barrier: An Enhanced Approximation Algorithm for Fault-Tolerant Minimum Weight Connected Dominating Set ⋮ Parsimonious formulations for low-diameter clusters ⋮ The Optimal Design of Low-Latency Virtual Backbones ⋮ A branch-and-Benders-cut approach for the fault tolerant regenerator location problem ⋮ A matheuristic approach for solving the 2-connected dominating set problem ⋮ Exact algorithms for the minimum \(s\)-club partitioning problem

This page was built for publication: An Integer Programming Approach for Fault-Tolerant Connected Dominating Sets