Premium
Minimum shared‐power edge cut
Author(s) -
Cabello Sergio,
Jain Kshitij,
Lubiw Anna,
Mondal Debajyoti
Publication year - 2020
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.21928
Subject(s) - rectangle , combinatorics , mathematics , time complexity , undirected graph , bounded function , unit disk graph , enhanced data rates for gsm evolution , dominating set , polynomial time approximation scheme , approximation algorithm , computational complexity theory , discrete mathematics , graph , matching (statistics) , minimum cut , computer science , algorithm , wireless network , wireless , vertex (graph theory) , statistics , geometry , mathematical analysis , telecommunications
We introduce a problem called 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, that is, without entering any disk. 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 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.