Colored Hypergraph Isomorphism is Fixed Parameter Tractable

We describe a fixed parameter tractable (fpt) algorithm for Colored Hypergraph Isomorphism , denoted CHI, which has running time (2 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 an fpt algorithm for a p...

Full description

Saved in:
Bibliographic Details
Published in:Algorithmica 2015-01, Vol.71 (1), p.120-138
Main Authors: Arvind, V., Das, Bireswar, Köbler, Johannes, Toda, Seinosuke
Format: Article
Language:English
Subjects:
Algorithm Analysis and Problem Complexity
Algorithms
Computer Science
Computer Systems Organization and Communication Networks
Data Structures and Information Theory
Mathematics of Computing
Theory of Computation
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We describe a fixed parameter tractable (fpt) algorithm for Colored Hypergraph Isomorphism , denoted CHI, which has running time (2 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 an fpt algorithm for a parameterized coset intersection problem that is used as a subroutine in our algorithm for CHI.
ISSN:0178-4617
1432-0541
DOI:10.1007/s00453-013-9787-y