The isomorphism problem for k-trees is complete for logspace

Show simple item record

dc.contributor.author Arvind, V.
dc.contributor.author Das, Bireswar
dc.contributor.author Köbler, Johannes
dc.contributor.author Kuhnert, Sebastian
dc.date.accessioned 2014-03-16T11:20:05Z
dc.date.available 2014-03-16T11:20:05Z
dc.date.issued 2012-08
dc.identifier.citation Das, Bireswar et al., “The isomorphism problem for k-trees is complete for logspace”, Information and Computation, DOI: 10.1016/j.ic.2012.04.002, vol. 217, pp. 1–11, Aug. 2012. en_US
dc.identifier.issn 0890-5401
dc.identifier.uri http://dx.doi.org/10.1016/j.ic.2012.04.002
dc.identifier.uri https://repository.iitgn.ac.in/handle/123456789/775
dc.description.abstract We show that, for k constant, k -tree isomorphism can be decided in logarithmic space by giving an View the MathML sourceO(klogn) space canonical labeling algorithm. The algorithm computes a unique tree decomposition, uses colors to fully encode the structure of the original graph in the decomposition tree and invokes Lindellʼs tree canonization algorithm. As a consequence, the isomorphism, the automorphism, as well as the canonization problem for k -trees are all complete for deterministic logspace. Completeness for logspace holds even for simple structural properties of k -trees. We also show that a variant of our canonical labeling algorithm runs in time View the MathML sourceO((k+1)!n), where n is the number of vertices, yielding the fastest known FPT algorithm for k-tree isomorphism. en_US
dc.description.statementofresponsibility by Bireswar Das et al.,
dc.format.extent Vol. 217, pp. 1–11
dc.language.iso en en_US
dc.publisher Elsevier en_US
dc.subject Graph isomorphism en_US
dc.subject Graph canonization en_US
dc.subject k-Trees en_US
dc.subject Logspace completeness en_US
dc.subject Space complexity en_US
dc.title The isomorphism problem for k-trees is complete for logspace en_US
dc.type Article en_US


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