Martin Schirneck

collaborators

6 papers

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

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.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 $I^$ , the data structure preprocesses a network $G = (V, E)$ and sensitivity parameter $f$ such that, for…