Surender Baswana is a faculty member at IIT Kanpur. Prior to joining IIT Kanpur, he was a Postdoctoral researcher at MPII (2003-06). Currently, he is a visiting scientist at Heinz Nixdorf Institute Paderborn, on sabbatical leave from IIT Kanpur. His research at Heinz Nixdorf Institute is supported by Alexander von Humboldt Fellowship for experienced researchers. His research interest lies in efficient algorithms for dynamic graphs.

AG 1   Info

AG Audience

English

45 Minutes

Saarbrücken

Let G be an undirected graph on n vertices and let k < n be any given positive integer. We address the problem of fault tolerant DFS tree defined as follows. Build a compact data structure that, given any set F of k failed vertices or edges, can efficiently report a depth first search tree of G\F. We present an algorithm which is drastically simpler and yet more efficient than the current state-of-the-art algorithms for this problem. Additionally, for achieving efficiency, the current-state-of-the-algorithms have to crucially rely on sophisticated data structures. The simplicity of our algorithm also results in replacing these sophisticated data structures by extremely simple and light data structures that occupy optimal space and take optimal preprocessing time. Our algorithm for the fault tolerant DFS tree also leads to a better time complexity for maintaining a DFS tree in a fully dynamic environment. (This is a joint work with Shiv Gupta and Ayush Tulsyan.)

Sándor Kisfaludi-Bak

--email hidden

passcode not visible

logged in users only