文章基本信息

标题：Colored Hypergraph Isomorphism is Fixed Parameter Tractable
本地全文：下载
作者：V. Arvind ; Bireswar Das ; Johannes K{\"o}bler 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2010
卷号：8
页码：327-337
DOI：10.4230/LIPIcs.FSTTCS.2010.327
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：Fixed parameter tractability; fpt algorithms; graph isomorphism; computational complexity