Minimum shared‐power edge cut

DOI10.1002/NET.21928MaRDI QIDQ6066053zbMATH OpenOpenAlexFDO

Authors S. Cabello, Kshitij Jain, Anna Lubiw, Debajyoti Mondal

Publication date 15 November 2023

Published in Networks (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1806.04742

zbMATH Keywords

wireless networkbarrier coverage\(s\)-\(t\) cutfully polynomial-time approximation schemeactivation network

Mathematics Subject Classification ID

Combinatorics (05-XX)

Abstract: We introduce a problem called the Minimum Shared-Power Edge Cut (MSPEC). The input to the problem is an undirected edge-weighted graph with distinguished vertices s and t, and the goal is to find an s-t cut by assigning "powers" at the vertices and removing an edge if the sum of the powers at its endpoints is at least its weight. The objective is to minimize the sum of the assigned powers. MSPEC is a graph generalization of a barrier coverage problem in a wireless sensor network: given a set of unit disks with centers in a rectangle, what is the minimum total amount by which we must shrink the disks to permit an intruder to cross the rectangle undetected, i.e. without entering any disc. This is a more sophisticated measure of barrier coverage than the minimum number of disks whose removal breaks the barrier. We develop a fully polynomial time approximation scheme (FPTAS) for MSPEC. We give polynomial time algorithms for the special cases where the edge weights are uniform, or the power values are restricted to a bounded set. Although MSPEC is related to network flow and matching problems, its computational complexity (in P or NP-hard) remains open.

Recommendations

• Minimum power partial multi-cover on a line
• Sharing energy for optimal edge performance
• On minimum power connectivity problems
• On Minimum Power Connectivity Problems
• Minimality of EDF networks with resource sharing
• Edge minimality of EDF resource sharing networks
• Min-power strong connectivity
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques

Cites work

• scientific article; zbMATH DE number 6865614 (Why is no real title available?)
• A Nearly Best-Possible Approximation Algorithm for Node-Weighted Steiner Trees
• A minimum spanning tree algorithm with inverse-Ackermann type complexity
• A randomized linear-time algorithm to find minimum spanning trees
• Algorithmic Aspects of Graph Connectivity
• An o(n^3 )-Time Maximum-Flow Algorithm
• An optimal minimum spanning tree algorithm
• Approximation algorithms for disjoint st-paths with minimum activation cost
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Coverage problems in sensor networks: a survey
• Exposure in wireless sensor networks: Theory and practical solutions
• Maximal Closure of a Graph and Applications to Combinatorial Problems
• Maximal flow through a domain
• Min-Power Covering Problems
• On maximum flows in polyhedral domains
• On minimum power connectivity problems
• On the complexity of barrier resilience for fat regions and bounded ply
• Power optimization for connectivity problems
• Simple and Fast Algorithms for Linear and Integer Programs with Two Variables Per Inequality
• Survivable network activation problems
• Survivable network design problems in wireless networks
• Tight bounds and 2-approximation algorithms for integer programs with two variables per inequality
• Union of random Minkowski sums and network vulnerability analysis

Cited in

(4)

• Exact and Approximate Algorithms for Computing a Second Hamiltonian Cycle
• Minimum cuts in geometric intersection graphs
• Hardness of minimum barrier shrinkage and minimum installation path
• Finding a Maximum Clique in a Grounded 1-Bend String Graph

This page was built for publication: Minimum shared‐power edge cut

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6066053)