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 |
|