11 citations · 61 across the 16 of their papers we have counts for
13 papers · 1 filter
FPT Isomorphism Test for -Free Tournaments
Daniel Neuen
We show that isomorphism of -free tournaments can be solved in FPT time , where denotes the size of , and denotes the size of the input tournamen…
Robust Graph Isomorphism, Quadratic Assignment and VC Dimension
Anatole Dahan, Martin Grohe, Daniel Neuen +1
We present an additive -approximation algorithm for the Graph Edit Distance problem (GED) on graphs of VC dimension running in time $n^{O(d/\varepsilon^{2})}…
Isomorphism for Tournaments of Small Twin Width
Martin Grohe, Daniel Neuen
We prove that isomorphism of tournaments of twin width at most can be decided in time . This implies that the isomorphism problem for classes of tourname…
The Iteration Number of the Weisfeiler-Leman Algorithm
Martin Grohe, Moritz Lichter, Daniel Neuen
We prove new upper and lower bounds on the number of iterations the -dimensional Weisfeiler-Leman algorithm (-WL) requires until stabilization. For , we show that $…
Isomorphism Testing for Graphs Excluding Small Topological Subgraphs
Daniel Neuen
We give an isomorphism test that runs in time on all -vertex graphs excluding some -vertex vertex graph as a topological subgraph. Previous re…
Recent Advances on the Graph Isomorphism Problem
Martin Grohe, Daniel Neuen
We give an overview of recent advances on the graph isomorphism problem. Our main focus will be on Babai's quasi-polynomial time isomorphism test and subsequent developments that l…
Isomorphism Testing for Graphs Excluding Small Minors
Martin Grohe, Daniel Neuen, Daniel Wiebking
We prove that there is a graph isomorphism test running in time on -vertex graphs excluding some -vertex graph as a minor. Previously known bo…
Hypergraph Isomorphism for Groups with Restricted Composition Factors
Daniel Neuen
We consider the isomorphism problem for hypergraphs taking as input two hypergraphs over the same set of vertices and a permutation group over domain , and asking whethe…
Canonisation and Definability for Graphs of Bounded Rank Width
Martin Grohe, Daniel Neuen
We prove that the combinatorial Weisfeiler-Leman algorithm of dimension is a complete isomorphism test for the class of all graphs of rank width at most . Rank width is…
An improved isomorphism test for bounded-tree-width graphs
Martin Grohe, Daniel Neuen, Pascal Schweitzer +1
We give a new fpt algorithm testing isomorphism of -vertex graphs of tree width in time , improving the fpt algorithm…
A Faster Isomorphism Test for Graphs of Small Degree
Martin Grohe, Daniel Neuen, Pascal Schweitzer
In a recent breakthrough, Babai (STOC 2016) gave a quasipolynomial time graph isomorphism test. In this work, we give an improved isomorphism test for graphs of small degree: our a…
Benchmark Graphs for Practical Graph Isomorphism
Daniel Neuen, Pascal Schweitzer
The state-of-the-art solvers for the graph isomorphism problem can readily solve generic instances with tens of thousands of vertices. Indeed, experiments show that on inputs witho…
Graph Isomorphism for unit square graphs
Daniel Neuen
In the past decades for more and more graph classes the Graph Isomorphism Problem was shown to be solvable in polynomial time. An interesting family of graph classes arises from in…