All reports by Author Fabian Wagner:

__
TR14-079
| 11th June 2014
__

Simon Straub, Thomas Thierauf, Fabian Wagner#### Counting the Number of Perfect Matchings in $K_5$-free Graphs

__
TR11-052
| 4th April 2011
__

Fabian Wagner#### On the Complexity of Group Isomorphism

Revisions: 4
,
Comments: 3

__
TR11-032
| 11th March 2011
__

Fabian Wagner#### Graphs of Bounded Treewidth can be Canonized in AC$^1$

__
TR10-117
| 22nd July 2010
__

Arkadev Chattopadhyay, Jacobo Toran, Fabian Wagner#### Graph Isomorphism is not AC^0 reducible to Group Isomorphism

__
TR10-050
| 25th March 2010
__

Samir Datta, Prajakta Nimbhorkar, Thomas Thierauf, Fabian Wagner#### Graph Isomorphism for $K_{3,3}$-free and $K_5$-free graphs is in Log-space

__
TR09-094
| 7th October 2009
__

Bireswar Das, Jacobo Toran, Fabian Wagner#### Restricted Space Algorithms for Isomorphism on Bounded Treewidth Graphs

__
TR09-052
| 2nd May 2009
__

Fabian Wagner, Samir Datta, Nutan Limaye, Prajakta Nimbhorkar, Thomas Thierauf#### Planar Graph Isomorphism is in Log-space

__
TR09-029
| 3rd April 2009
__

Fabian Wagner, Thomas Thierauf#### Reachability in K_{3,3}-free Graphs and K_5-free Graphs is in Unambiguous Log-Space

Revisions: 1

__
TR07-068
| 24th July 2007
__

Thomas Thierauf, Fabian Wagner#### The Isomorphism Problem for Planar 3-Connected Graphs is in Unambiguous Logspace

Simon Straub, Thomas Thierauf, Fabian Wagner

Counting the number of perfect matchings in arbitrary graphs is a $\#$P-complete problem. However, for some restricted classes of graphs the problem can be solved efficiently. In the case of planar graphs, and even for $K_{3,3}$-free graphs, Vazirani showed that it is in NC$^2$. The technique there is to compute ... more >>>

Fabian Wagner

The group isomorphism problem consists in deciding whether two groups $G$ and $H$

given by their multiplication tables are isomorphic.

An algorithm for group isomorphism attributed to Tarjan runs in time $n^{\log n + O(1)}$, c.f. [Mil78].

Miller and Monk showed in [Mil79] that group isomorphism can be many-one ... more >>>

Fabian Wagner

In recent results the complexity of isomorphism testing on

graphs of bounded treewidth is improved to TC$^1$ [GV06] and further to LogCFL [DTW10].

The computation of canonical forms or a canonical labeling provides more information than

isomorphism testing.

Whether canonization is in NC or even TC$^1$ was stated ...
more >>>

Arkadev Chattopadhyay, Jacobo Toran, Fabian Wagner

We give a new upper bound for the Group and Quasigroup

Isomorphism problems when the input structures

are given explicitly by multiplication tables. We show that these problems can be computed by polynomial size nondeterministic circuits of unbounded fan-in with $O(\log\log n)$ depth and $O(\log^2 n)$ nondeterministic bits, ...
more >>>

Samir Datta, Prajakta Nimbhorkar, Thomas Thierauf, Fabian Wagner

Graph isomorphism is an important and widely studied computational problem, with

a yet unsettled complexity.

However, the exact complexity is known for isomorphism of various classes of

graphs. Recently [DLN$^+$09] proved that planar graph isomorphism is complete for log-space.

We extend this result of [DLN$^+$09] further

to the ...
more >>>

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 \cite{Bo90},\cite{YBFT}.

We give restricted space algorithms for these problems proving the following results:

Isomorphism for bounded tree distance width graphs is in L and thus complete ... more >>>

Fabian Wagner, Samir Datta, Nutan Limaye, Prajakta Nimbhorkar, Thomas Thierauf

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. There is a significant gap between extant lower and upper bounds for planar graphs as well. We bridge the gap for this natural and ... more >>>

Fabian Wagner, Thomas Thierauf

We show that the reachability problem for directed graphs

that are either K_{3,3}-free or K_5-free

is in unambiguous log-space, UL \cap coUL.

This significantly extends the result of Bourke, Tewari, and Vinodchandran

that the reachability problem for directed planar graphs

is in UL \cap coUL.

Our algorithm decomposes ... more >>>

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, it is in the class AC^1.

In this paper we improve the upper bound for planar 3-connected graphs to unambiguous logspace, in fact to ... more >>>