Showing cs.DSShow all
3 papers · 1 filter
cs.DS2021
Algorithms and data structures for first-order logic with connectivity under vertex failures
Michał Pilipczuk, Nicole Schirrmacher, Sebastian Siebertz +2
We introduce a new data structure for answering connectivity queries in undirected graphs subject to batched vertex failures. Precisely, given any graph G and integer k, we can in…
cs.DS2021
Recursive Backdoors for SAT
Nikolas Mählmann, Sebastian Siebertz, Alexandre Vigny
A strong backdoor in a formula of propositional logic to a tractable class of formulas is a set of variables of such that every assignment of the variable…
cs.DS2020
Constant round distributed domination on graph classes with bounded expansion
Simeon Kublenz, Sebastian Siebertz, Alexandre Vigny
We show that the dominating set problem admits a constant factor approximation in a constant number of rounds in the LOCAL model of distributed computing on graph classes with boun…