13 citations · 70 across the 27 of their papers we have counts for
45 papers
Exploration of graphs with excluded minors
Julia Baligacs, Yann Disser, Irene Heinrich +1
We study the online graph exploration problem proposed by Kalyanasundaram and Pruhs (1994) and prove a constant competitive ratio on minor-free graphs. This result encompasses and…
Compressing CFI Graphs and Lower Bounds for the Weisfeiler-Leman Refinements
Martin Grohe, Moritz Lichter, Daniel Neuen +1
The -dimensional Weisfeiler-Leman (-WL) algorithm is a simple combinatorial algorithm that was originally designed as a graph isomorphism heuristic. It naturally finds applic…
Algorithms Transcending the SAT-Symmetry Interface
Markus Anders, Pascal Schweitzer, Mate Soos
Dedicated treatment of symmetries in satisfiability problems (SAT) is indispensable for solving various classes of instances arising in practice. However, the exploitation of symme…
Engineering a Preprocessor for Symmetry Detection
Markus Anders, Pascal Schweitzer, Julian Stieß
State-of-the-art solvers for symmetry detection in combinatorial objects are becoming increasingly sophisticated software libraries. Most of the solvers were initially designed wit…
Choiceless Polynomial Time with Witnessed Symmetric Choice
Moritz Lichter, Pascal Schweitzer
We extend Choiceless Polynomial Time (CPT), the currently only remaining promising candidate in the quest for a logic capturing PTime, so that this extended logic has the following…
A systematic approach to random data augmentation on graph neural networks
Billy Joe Franks, Markus Anders, Marius Kloft +1
Random data augmentations (RDAs) are state of the art regarding practical graph neural networks that are provably universal. There is great diversity regarding terminology, methodo…