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

New for: D1
<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:Fault Tolerant Reachability Subgraph : Generic and Optimal
Speaker:Keerti Choudhary
coming from:IIT Kanpur
Speakers Bio:
Event Type:AG1 Mittagsseminar (own work)
We use this to send out email in the morning.
Level:AG Audience
Date, Time and Location
Date:Thursday, 16 July 2015
Duration:30 Minutes
Building:E1 4
Let G=(V,E) be a directed graph with n vertices, and s be any designated source vertex. We address the problem of computing a sparse fault-tolerant reachability structure (or FTRS for short), namely, a subgraph H of G such that on failure of any k edges or vertices, the set of vertices reachable from s in G\F is the same as the set of vertices reachable from s in H\F. We present an algorithm for constructing an FTRS with O(2^k n) edges, and also provide a matching lower bound result.
Name(s):Andreas Wiese
EMail:--email address not disclosed on the web
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Attachments, File(s):
  • Andreas Wiese, 07/16/2015 01:48 PM
  • Andreas Wiese, 07/13/2015 01:05 PM
  • Andreas Wiese, 07/01/2015 07:30 PM -- Created document.