Campus Event Calendar
Event Entry
New for: D1
What and Who
Fault Tolerant Reachability Subgraph : Generic and Optimal
Keerti Choudhary
IIT Kanpur
AG1 Mittagsseminar (own work)
AG 1
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Thursday, 16 July 2015
13:00
30 Minutes
E1 4
024
Saarbrücken
Abstract
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.
Contact
Andreas Wiese
--email hidden
passcode not visible
logged in users only
Andreas Wiese, 07/16/2015 13:48
Andreas Wiese, 07/13/2015 13:05
Andreas Wiese, 07/01/2015 19:30 -- Created document.
Andreas Wiese, 07/13/2015 13:05
Andreas Wiese, 07/01/2015 19:30 -- Created document.