4 citations · 6 across the 9 of their papers we have counts for
4 papers · 1 filter
Can We Break Fine-Grained and NP-Hardness Barriers if We've Seen the Graph Before? The Isomorphic-Priors Model
Dani Dorfmann, Dani Dorfman, Simon Döring +5
If we run a heavy-duty computation on prior data, can we avoid repeated computation for similar future inputs? Inspired by this question, we introduce a new computational model for…
The Classical Weisfeiler-Leman Algorithm Stabilizes in Rounds
Simon Döring, Daniel Neuen
The classical Weisfeiler-Leman algorithm (also known as the -dimensional Weisfeiler-Leman algorithm) is a simple combinatorial algorithm that was originally designed as a heuris…
A Dense Weisfeiler-Leman Algorithm for Deciding Bounded-Cliquewidth Homomorphism Indistinguishability
Radu Curticapean, Daniel Neuen, Amir Nikabadi +2
Two graphs and are homomorphism indistinguishable over a graph class if they admit the same number of homomorphisms from every graph in . A wide…
Distinguishing Graphs by Counting Homomorphisms from Sparse Graphs
Daniel Neuen, Tim Seppelt
Lovász (1967) showed that two graphs and are isomorphic if, and only if, they are homomorphism indistinguishable over all graphs, i.e., and admit the same number of…