首页    期刊浏览 2024年11月28日 星期四
登录注册

文章基本信息

  • 标题: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
国家哲学社会科学文献中心版权所有