9 citations · 11 across the 12 of their papers we have counts for
21 papers
Implicit Hitting Set Enumeration for Power Dominating Sets
Thomas Bläsius, Max Göttlicher, Martin Schirneck
The Transversal Hypergraph problem asks to enumerate (list) all inclusion-minimal hitting sets of a hypergraph. It usually assumes that the input is completely known and does not c…
Near-Optimal Replacement Path Coverings
Davide Bilò, Keerti Choudhary, Sarel Cohen +1
Let and be positive integers. An -replacement path covering (RPC) for a graph is a family of subgraphs such that, for every set of at most …
Minimal-to-Maximal Conversion Search Is Not Output-Polynomial
Bennet Hörmann, Martin Schirneck
The Transversal Hypergraph problem is to enumerate (list) all inclusion-wise minimal hitting sets of a given hypergraph . It is the most important open question in enu…
Simpler and Improved Replacement Path Coverings
Davide Bilò, Shiri Chechik, Keerti Choudhary +2
An important tool in the design of fault-tolerant graph data structures are -replacement path coverings (RPCs). An RPC is a family of subgraphs of a given grap…
Transversal Rank, Conformality and Enumeration
Martin Schirneck
The transversal rank of a hypergraph is the maximum size of its minimal hitting sets. Deciding, for an -vertex, -edge hypergraph and an integer , whether the transversal r…
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…
Improved Distance (Sensitivity) Oracles with Subquadratic Space
Davide Bilò, Shiri Chechik, Keerti Choudhary +3
A distance oracle (DO) with stretch for a graph is a data structure that, when queried with vertices and , returns a value such that $d(s,t)…
Improved Approximate Distance Oracles: Bypassing the Thorup-Zwick Bound in Dense Graphs
Davide Bilò, Shiri Chechik, Keerti Choudhary +3
Despite extensive research on distance oracles, there are still large gaps between the best constructions for spanners and distance oracles. Notably, there exist sparse spanners wi…
Approximate Distance Sensitivity Oracles in Subquadratic Space
Davide Bilò, Shiri Chechik, Keerti Choudhary +4
An -edge fault-tolerant distance sensitive oracle (-DSO) with stretch is a data structure that preprocesses a given undirected, unweighted graph with vertice…
Fault-Tolerant ST-Diameter Oracles
Davide Bilò, Keerti Choudhary, Sarel Cohen +3
Given two vertex sets and in a graph, the -diameter is the maximum --distance between vertices and . We study the problem of estimating the $ST…
Compact Distance Oracles with Large Sensitivity and Low Stretch
Davide Bilò, Keerti Choudhary, Sarel Cohen +3
An -edge fault-tolerant distance sensitive oracle (-DSO) with stretch is a data structure that preprocesses an input graph . When queried with the triple $(s,t,F…
Fair Correlation Clustering in Forests
Katrin Casel, Tobias Friedrich, Martin Schirneck +1
The study of algorithmic fairness received growing attention recently. This stems from the awareness that bias in the input data for machine learning systems may result in discrimi…
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…
Fixed-Parameter Sensitivity Oracles
Davide Bilò, Katrin Casel, Keerti Choudhary +5
We combine ideas from distance sensitivity oracles (DSOs) and fixed-parameter tractability (FPT) to design sensitivity oracles for FPT graph problems. An oracle with sensitivity $f…
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…
timeXplain -- A Framework for Explaining the Predictions of Time Series Classifiers
Felix Mujkanovic, Vanja Doskoč, Martin Schirneck +2
Modern time series classifiers display impressive predictive capabilities, yet their decision-making processes mostly remain black boxes to the user. At the same time, model-agnost…
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…
Understanding the Effectiveness of Data Reduction in Public Transportation Networks
Thomas Bläsius, Philipp Fischbeck, Tobias Friedrich +1
Given a public transportation network of stations and connections, we want to find a minimum subset of stations such that each connection runs through a selected station. Although…
Efficiently Enumerating Hitting Sets of Hypergraphs Arising in Data Profiling
Thomas Bläsius, Tobias Friedrich, Julius Lischeid +2
The transversal hypergraph problem is the task of enumerating the minimal hitting sets of a hypergraph. It is a long-standing open question whether this can be done in output-polyn…