max planck institut
informatik
informatik
| New for: D1 |
| << Previous Entry | Next Entry >> | New Event Entry | Edit this Entry | Login to DB (to update, delete) |
| Title: | Fault Tolerant Reachability Subgraph : Generic and Optimal |
|---|---|
| Speaker: | Keerti Choudhary |
| coming from: | IIT Kanpur |
| Speakers Bio: | |
| Event Type: | AG1 Mittagsseminar (own work) |
| Visibility: | D1 We use this to send out email in the morning. |
| Level: | AG Audience |
| Language: | English |
| Date: | Thursday, 16 July 2015 |
|---|---|
| Time: | 13:00 |
| Duration: | 30 Minutes |
| Location: | Saarbrücken |
| Building: | E1 4 |
| Room: | 024 |
| 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: | No | To Location: |
|---|
| Note: | |
|---|---|
| Attachments, File(s): |