All reports by Author Seinosuke Toda:

__
TR09-093
| 8th October 2009
__

Vikraman Arvind, Bireswar Das, Johannes Köbler, Seinosuke Toda#### Colored Hypergraph Isomorphism is Fixed Parameter Tractable

Revisions: 1

__
TR01-061
| 13th July 2001
__

Mitsunori Ogihara, Seinosuke Toda#### The Complexity of Computing the Number of Self-Avoiding Walks in Two-Dimensional Grid Graphs and in Hypercube Graphs

Revisions: 2

Vikraman Arvind, Bireswar Das, Johannes Köbler, Seinosuke Toda

We describe a fixed parameter tractable (fpt) algorithm for Colored Hypergraph Isomorphism} which has running time $b!2^{O(b)}N^{O(1)}$, where the parameter $b$ is the maximum size of the color classes of the given hypergraphs and $N$ is the input size. We also describe fpt algorithms for certain permutation group problems that ... more >>>

Mitsunori Ogihara, Seinosuke Toda

Valiant (SIAM Journal on Computing 8, pages 410--421) showed that the

roblem of counting the number of s-t paths in graphs (both in the case

of directed graphs and in the case of undirected graphs) is complete

for #P under polynomial-time one-Turing reductions (namely, some

post-computation is needed to ...
more >>>