Solving the Connected Dominating Set Problem and Power Dominating Set Problem by Integer Programming
From MaRDI portal
Publication:3167378
DOI10.1007/978-3-642-31770-5_33zbMath1358.05214OpenAlexW68141807MaRDI QIDQ3167378
Publication date: 2 November 2012
Published in: Combinatorial Optimization and Applications (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-31770-5_33
integer programmingspanning treeconnected subgraphconnected dominating set problempower dominating set problem
Integer programming (90C10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items (25)
An improved binary programming formulation for the secure domination problem ⋮ Optimization of wireless sensor networks deployment with coverage and connectivity constraints ⋮ Computational approaches for zero forcing and related problems ⋮ Domination type parameters of Pell graphs ⋮ The \(k\)-hop connected dominating set problem: hardness and polyhedra ⋮ Flow-based formulation for the maximum leaf spanning tree problem ⋮ Hardness results of connected power domination for bipartite graphs and chordal graphs ⋮ Spanning trees with a constraint on the number of leaves. A new formulation ⋮ Benders Decomposition, Branch-and-Cut, and Hybrid Algorithms for the Minimum Connected Dominating Set Problem ⋮ New computational approaches for the power dominating set problem: Set covering and the neighborhoods of zero forcing forts ⋮ Binary programming formulations for the upper domination problem ⋮ An integer program for positive semidefinite zero forcing in graphs ⋮ Asymmetric probabilistic minimum-cost Hamiltonian cycle problem considering arc and vertex failures ⋮ Solving the multistage PMU placement problem by integer programming and equivalent network design model ⋮ Restricted power domination and zero forcing problems ⋮ Connected power domination in graphs ⋮ Complexity and lowers bounds for power edge set problem ⋮ The Optimal Design of Low-Latency Virtual Backbones ⋮ Regenerator location problem: polyhedral study and effective branch-and-cut algorithms ⋮ Complexity and computation of connected zero forcing ⋮ On the minimum-cost \(\lambda\)-edge-connected \(k\)-subgraph problem ⋮ The probabilistic and reliable connected power dominating set problems ⋮ Efficient Local Search based on Dynamic Connectivity Maintenance for Minimum Connected Dominating Set ⋮ Algorithmic complexity of weakly connected Roman domination in graphs ⋮ On connected dominating sets of restricted diameter
This page was built for publication: Solving the Connected Dominating Set Problem and Power Dominating Set Problem by Integer Programming
