ECCC-Report TR09-093https://eccc.weizmann.ac.il/report/2009/093Comments and Revisions published for TR09-093en-usThu, 15 Apr 2010 18:15:26 +0300
Revision 1
| Colored Hypergraph Isomorphism is Fixed Parameter Tractable |
Vikraman Arvind,
Bireswar Das,
Johannes Köbler,
Seinosuke Toda
https://eccc.weizmann.ac.il/report/2009/093#revision1We 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.Thu, 15 Apr 2010 18:15:26 +0300https://eccc.weizmann.ac.il/report/2009/093#revision1
Paper TR09-093
| Colored Hypergraph Isomorphism is Fixed Parameter Tractable |
Vikraman Arvind,
Bireswar Das,
Johannes Köbler,
Seinosuke Toda
https://eccc.weizmann.ac.il/report/2009/093We 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.Fri, 09 Oct 2009 20:59:00 +0200https://eccc.weizmann.ac.il/report/2009/093