Martin Schirneck

activity

20182026

most citedtimeXplain -- A Framework for Explaining the Predictions of Time Series Classifiers

9 citations · 11 across the 12 of their papers we have counts for

collaborators

Showing cs.DSShow all

17 papers · 1 filter

cs.DS2026

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…

cs.DS2026

Near-Optimal Replacement Path Coverings

Davide Bilò, Keerti Choudhary, Sarel Cohen +1

Let $L$ and $f$ be positive integers. An $(L, f)$ -replacement path covering (RPC) for a graph $G$ is a family $G$ of subgraphs such that, for every set $F$ of at most $f$ …

cs.DS2026

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 $H$ . It is the most important open question in enu…

cs.DS2026

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 $(L, f)$ -replacement path coverings (RPCs). An RPC is a family $G$ of subgraphs of a given grap…

cs.DS2026

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 $n$ -vertex, $m$ -edge hypergraph and an integer $k$ , whether the transversal r…

cs.DS2024

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 $G = (V, E)$ and sensitivity parameter $f$ such that, for…

cs.DS2024

Improved Distance (Sensitivity) Oracles with Subquadratic Space

Davide Bilò, Shiri Chechik, Keerti Choudhary +3

A distance oracle (DO) with stretch $(α, β)$ for a graph $G$ is a data structure that, when queried with vertices $s$ and $t$ , returns a value $d (s, t)$ such that $d(s,t)…

cs.DS2023

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…

cs.DS2023★ 2 cited

Approximate Distance Sensitivity Oracles in Subquadratic Space

Davide Bilò, Shiri Chechik, Keerti Choudhary +4

An $f$ -edge fault-tolerant distance sensitive oracle ( $f$ -DSO) with stretch $σ \geq 1$ is a data structure that preprocesses a given undirected, unweighted graph $G$ with $n$ vertice…

cs.DS2023

Fault-Tolerant ST-Diameter Oracles

Davide Bilò, Keerti Choudhary, Sarel Cohen +3

Given two vertex sets $S$ and $T$ in a graph, the $S T$ -diameter is the maximum $s$ - $t$ -distance between vertices $s \in S$ and $t \in T$ . We study the problem of estimating the $ST…

cs.DS2023

Compact Distance Oracles with Large Sensitivity and Low Stretch

Davide Bilò, Keerti Choudhary, Sarel Cohen +3

An $f$ -edge fault-tolerant distance sensitive oracle ( $f$ -DSO) with stretch $σ \geq 1$ is a data structure that preprocesses an input graph $G$ . When queried with the triple $(s,t,F…

cs.DS2022

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…

cs.DS2021

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…

cs.DS2021

Space-Efficient Fault-Tolerant Diameter Oracles

Davide Bilò, Sarel Cohen, Tobias Friedrich +1

We design $f$ -edge fault-tolerant diameter oracles ( $f$ -FDOs). We preprocess a given graph $G$ on $n$ vertices and $m$ edges, and a positive integer $f$ , to construct a data struct…

cs.DS2021

Near-Optimal Deterministic Single-Source Distance Sensitivity Oracles

Davide Bilò, Sarel Cohen, Tobias Friedrich +1

Given a graph with a source vertex $s$ , the Single Source Replacement Paths (SSRP) problem is to compute, for every vertex $t$ and edge $e$ , the length $d (s, t, e)$ of a shortest pat…

cs.DS2021

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…

cs.DS2018

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…