4 citations · 4 across the 1 of their papers we have counts for
4 papers
Beating the Generator-Enumeration Bound for -Group Isomorphism
David J. Rosenbaum, Fabian Wagner
We consider the group isomorphism problem: given two finite groups G and H specified by their multiplication tables, decide if G cong H. For several decades, the n^(log_p n + O(1))…
Restricted Space Algorithms for Isomorphism on Bounded Treewidth Graphs
Bireswar Das, Jacobo Toran, Fabian Wagner
The Graph Isomorphism problem restricted to graphs of bounded treewidth or bounded tree distance width are known to be solvable in polynomial time [Bod90],[YBFT99]. We give restric…
A Log-space Algorithm for Canonization of Planar Graphs
Samir Datta, Nutan Limaye, Prajakta Nimbhorkar +2
Graph Isomorphism is the prime example of a computational problem with a wide difference between the best known lower and upper bounds on its complexity. We bridge this gap for a n…
The Isomorphism Problem for Planar 3-Connected Graphs is in Unambiguous Logspace
Thomas Thierauf, Fabian Wagner
The isomorphism problem for planar graphs is known to be efficiently solvable. For planar 3-connected graphs, the isomorphism problem can be solved by efficient parallel algorithms…