<?xml version="1.0" encoding="UTF-8"?><?xml-stylesheet type="text/xsl" href="static/style.xsl"?><OAI-PMH xmlns="http://www.openarchives.org/OAI/2.0/" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.openarchives.org/OAI/2.0/ http://www.openarchives.org/OAI/2.0/OAI-PMH.xsd"><responseDate>2026-11-22T07:20:09Z</responseDate><request verb="GetRecord" identifier="oai:uwspace.uwaterloo.ca:10012/13664" metadataPrefix="dim">https://dspacemainprd01.lib.uwaterloo.ca/server/oai/request</request><GetRecord><record><header><identifier>oai:uwspace.uwaterloo.ca:10012/13664</identifier><datestamp>2025-03-26T23:36:18Z</datestamp><setSpec>com_10012_9924</setSpec><setSpec>com_10012_1</setSpec><setSpec>col_10012_9930</setSpec><setSpec>col_10012_6</setSpec></header><metadata><dim:dim xmlns:dim="http://www.dspace.org/xmlns/dspace/dim" xmlns:doc="http://www.lyncode.com/xoai" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.dspace.org/xmlns/dspace/dim http://www.dspace.org/schema/dim.xsd">
   <dim:field mdschema="dc" element="contributor" qualifier="advisor">Lubiw, Anna</dim:field>
   <dim:field mdschema="dc" element="contributor" qualifier="author" authority="1a24521b-1631-4df5-a21a-ed820632454f" confidence="600">Jain, Kshitij</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="accessioned">2018-08-24T15:30:43Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="available">2018-08-24T15:30:43Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="issued">2018-08-24</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="submitted">2018-08-01</dim:field>
   <dim:field mdschema="dc" element="identifier" qualifier="uri">http://hdl.handle.net/10012/13664</dim:field>
   <dim:field mdschema="dc" element="description" qualifier="abstract" lang="en">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 &amp;quot;powers&amp;quot; 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.&#xd;
&#xd;
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.&#xd;
&#xd;
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.</dim:field>
   <dim:field mdschema="dc" element="language" qualifier="iso" lang="en">en</dim:field>
   <dim:field mdschema="dc" element="publisher" lang="en">University of Waterloo</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">Algorithms</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">Computational Geometry</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">Approximation Algorithm</dim:field>
   <dim:field mdschema="dc" element="title" lang="en">Minimum Shared-Power Edge Cut</dim:field>
   <dim:field mdschema="dc" element="type" lang="en">Master Thesis</dim:field>
   <dim:field mdschema="dc" element="pending">false</dim:field>
   <dim:field mdschema="uws-etd" element="degree" qualifier="department" lang="en">David R. Cheriton School of Computer Science</dim:field>
   <dim:field mdschema="uws-etd" element="degree" qualifier="discipline" lang="en">Computer Science</dim:field>
   <dim:field mdschema="uws-etd" element="degree" qualifier="grantor" lang="en">University of Waterloo</dim:field>
   <dim:field mdschema="uws-etd" element="degree" lang="en">Master of Mathematics</dim:field>
   <dim:field mdschema="uws" element="contributor" qualifier="advisor">Lubiw, Anna</dim:field>
   <dim:field mdschema="uws" element="contributor" qualifier="affiliation1" lang="en">Faculty of Mathematics</dim:field>
   <dim:field mdschema="uws" element="published" qualifier="city" lang="en">Waterloo</dim:field>
   <dim:field mdschema="uws" element="published" qualifier="country" lang="en">Canada</dim:field>
   <dim:field mdschema="uws" element="published" qualifier="province" lang="en">Ontario</dim:field>
   <dim:field mdschema="uws" element="typeOfResource" lang="en">Text</dim:field>
   <dim:field mdschema="uws" element="peerReviewStatus" lang="en">Unreviewed</dim:field>
   <dim:field mdschema="uws" element="scholarLevel" lang="en">Graduate</dim:field>
   <dim:field mdschema="others" element="access-status">open.access</dim:field>
</dim:dim>
</metadata></record></GetRecord></OAI-PMH>