Revision #1 Authors: Vikraman Arvind, Bireswar Das, Johannes Köbler, Seinosuke Toda

Accepted on: 15th April 2010 18:15

Downloads: 2279

Keywords:

We describe a fixed parameter tractable (fpt) algorithm for Colored Hypergraph Isomorphism} which has running time $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 are used as subroutines in our algorithm.

By using a divide and conquer technique similar to Luks [Luk99] we improve the running time of our fpt algorithm for Colored Hypergraph Isomorphism from $b!2^{O(b)}N^{O(1)}$ to $2^{O(b)}N^{O(1)}$. Further we describe an $N^{O(b)}$ time canonization algorithm for colored hypergraphs.

TR09-093 Authors: Vikraman Arvind, Bireswar Das, Johannes Köbler, Seinosuke Toda

Publication: 9th October 2009 20:59

Downloads: 2169

Keywords:

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 are used as subroutines in our algorithm.