Colored hypergraph isomorphism is fixed parameter tractable

Show simple item record Arvind, V. Das, Bireswar Kobler, Johannes Toda, Seinosuke 2015-01-17T11:11:34Z 2015-01-17T11:11:34Z 2015-01
dc.identifier.citation Arvind, V.; Das, Bireswar; Köbler, Johannes and Toda, Seinosuke, “Colored hypergraph isomorphism is fixed parameter tractable”, Algorithmica, DOI: 10.1007/s00453-013-9787-y, Apr. 2013. en_US
dc.identifier.issn 1432-0541
dc.description.abstract 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. en_US
dc.description.statementofresponsibility by V. Arvind, Bireswar Das, Johannes Kobler and Seinosuke Toda
dc.format.extent vol. 71, no. 1, pp. 120-138
dc.language.iso en en_US
dc.publisher Springer en_US
dc.subject Fixed parameter tractability en_US
dc.subject Fpt algorithms en_US
dc.subject Graph isomorphism en_US
dc.subject Computational complexity en_US
dc.title Colored hypergraph isomorphism is fixed parameter tractable en_US
dc.type Article en_US
dc.relation.journal Algorithmica

Files in this item

Files Size Format View

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record

Search Digital Repository


My Account