7 papers
Efficient Fault-Tolerant Search by Fast Indexing of Subnetworks
Davide Bilò, Keerti Choudhary, Sarel Cohen +2
We design sensitivity oracles for error-prone networks. For a network problem , the data structure preprocesses a network and sensitivity parameter such that, for…
Deterministic Sensitivity Oracles for Diameter, Eccentricities and All Pairs Distances
Davide Bilò, Keerti Choudhary, Sarel Cohen +2
We construct data structures for extremal and pairwise distances in directed graphs in the presence of transient edge failures. Henzinger et al. [ITCS 2017] initiated the study of…
Space-Efficient Fault-Tolerant Diameter Oracles
Davide Bilò, Sarel Cohen, Tobias Friedrich +1
We design -edge fault-tolerant diameter oracles (-FDOs). We preprocess a given graph on vertices and edges, and a positive integer , to construct a data struct…
Near-Optimal Deterministic Single-Source Distance Sensitivity Oracles
Davide Bilò, Sarel Cohen, Tobias Friedrich +1
Given a graph with a source vertex , the Single Source Replacement Paths (SSRP) problem is to compute, for every vertex and edge , the length of a shortest pat…
The Complexity of Dependency Detection and Discovery in Relational Databases
Thomas Bläsius, Tobias Friedrich, Martin Schirneck
Multi-column dependencies in relational databases come associated with two different computational tasks. The detection problem is to decide whether a dependency of a certain type…
The Minimization of Random Hypergraphs
Thomas Bläsius, Tobias Friedrich, Martin Schirneck
We investigate the maximum-entropy model for random -vertex, -edge multi-hypergraphs with expected edge size . We show that the expected size of the…