Colored hypergraph isomorphism is fixed parameter tractable

Show simple item record

dc.contributor.author Arvind, V.
dc.contributor.author Das, Bireswar
dc.contributor.author Kobler, Johannes
dc.contributor.author Toda, Seinosuke
dc.date.accessioned 2015-01-17T11:11:34Z
dc.date.available 2015-01-17T11:11:34Z
dc.date.issued 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.identifier.uri http://dx.doi.org/10.1007/s00453-013-9787-y
dc.identifier.uri https://repository.iitgn.ac.in/handle/123456789/1545
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


Browse

My Account