92 citations · 106 across the 20 of their papers we have counts for
4 papers · 1 filter
Path Odd-Covers of Graphs
Steffen Borgwardt, Calum Buchanan, Eric Culver +3
We introduce and study "path odd-covers", a weakening of Gallai's path decomposition problem and a strengthening of the linear arboricity problem. The "path odd-cover number" $p_2(…
Canonizing Graphs of Bounded Rank-Width in Parallel via Weisfeiler--Leman
Michael Levet, Puck Rombach, Nicholas Sieger
In this paper, we show that computing canonical labelings of graphs of bounded rank-width is in . Our approach builds on the framework of Köbler & Verbitsky (CSR 2…
Generating Dominating Sets Using Locally-Defined Centrality Measures
Hunter Rehm, Robert Kassouf-Short, Puck Rombach
The dominating set problem has many practical applications but is well-known to be NP-hard. Therefore, there is a need for efficient approximation algorithms, especially in applica…
Logarithmic Weisfeiler--Leman and Treewidth
Michael Levet, Puck Rombach, Nicholas Sieger
In this paper, we show that the -dimensional Weisfeiler--Leman algorithm can identify graphs of treewidth in rounds. This improves the result of Grohe & Ver…