Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

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

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 >>>

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

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 >>>

ISSN 1433-8092 | Imprint