4 papers
Fault-Tolerant Distance Oracles Below the Barrier
Sanjeev Khanna, Christian Konrad, Aaron Putterman
Fault-tolerant spanners are fundamental objects that preserve distances in graphs even under edge failures. A long line of work culminating in Bodwin, Dinitz, Robelle (SODA 2022) g…
Constructing Long Paths in Graph Streams
Christian Konrad, Chhaya Trehan
In the graph stream model of computation, an algorithm processes the edges of an input graph in one or more sequential passes while using a memory sublinear in the input size. This…
Streaming Maximal Matching with Bounded Deletions
Sanjeev Khanna, Christian Konrad, Jacques Dark
We initiate the study of the Maximal Matching problem in bounded-deletion graph streams. In this setting, a graph is revealed as an arbitrary sequence of edge insertions and de…
Graph Reconstruction via MIS Queries
Christian Konrad, Conor O'Sullivan, Victor Traistaru
In the Graph Reconstruction (GR) problem, a player initially only knows the vertex set of an input graph and is required to learn its set of edges . To this end,…