1 citations · 2 across the 11 of their papers we have counts for
5 papers · 1 filter
Local planar domination revisited
Ozan Heydt, Sebastian Siebertz, Alexandre Vigny
We show how to compute a 20-approximation of a minimum dominating set in a planar graph in a constant number of rounds in the LOCAL model of distributed computing. This improves on…
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…
First-Order Logic with Connectivity Operators
Nicole Schirrmacher, Sebastian Siebertz, Alexandre Vigny
First-order logic (FO) can express many algorithmic problems on graphs, such as the independent set and dominating set problem, parameterized by solution size. On the other hand, F…
Discrepancy and Sparsity
Mario Grobler, Yiting Jiang, Patrice Ossona de Mendez +2
We study the connections between the notions of combinatorial discrepancy and graph degeneracy. In particular, we prove that the maximum discrepancy over all subgraphs of a gra…
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…