Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:Tracking Routes in Communication Networks
Speaker:Stefano Leucci
coming from:Max-Planck-Institut für Informatik - D1
Speakers Bio:
Event Type:AG1 Mittagsseminar (own work)
Visibility:D1, MMCI
We use this to send out email in the morning.
Level:AG Audience
Date, Time and Location
Date:Monday, 17 June 2019
Duration:30 Minutes
Building:E1 4
The minimum tracking set problem is an optimization problem that deals with monitoring communication paths that can be used for exchanging point-to-point messages using as few tracking devices as possible. More precisely, a tracking set of a given graph $G$ and a set of source-destination pairs of vertices, is a subset $T$ of vertices of $G$ such that the vertices in $T$ traversed by any source-destination shortest path $P$ uniquely identify $P$.

The minimum tracking set problem has been introduced in [Banik et al., CIAC 2017] for the case of a single source-destination pair.
There, the authors show that the problem is APX-hard and that it can be 2-approximated for the class of planar graphs, even though no hardness result is known for this case.
In this paper we focus on the case of multiple source-destination pairs and we present the first $\widetilde{O}(\sqrt{n})$-approximation algorithm for general graphs. Moreover, we prove that the problem remains NP-hard even for cubic planar graphs and all pairs $S \times D$, where $S$ and $D$ are the sets of sources and destinations, respectively.
Finally, for the case of a single source-destination pair, we design an (exact) FPT algorithm w.r.t. the maximum number of vertices at the same distance from the source.

Name(s):Nitin Saurabh
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Attachments, File(s):
  • Nitin Saurabh, 06/13/2019 12:32 PM
  • Nitin Saurabh, 06/11/2019 02:41 PM -- Created document.