7 citations · 8 across the 6 of their papers we have counts for
4 papers · 1 filter
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…
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…
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…
On the Parameterized Complexity of Reconfiguration of Connected Dominating Sets
Daniel Lokshtanov, Amer E. Mouawad, Fahad Panolan +1
In a reconfiguration version of an optimization problem the input is an instance of and two feasible solutions and . The objective is to determin…