The isomorphism problem for k-trees is complete for logspace

Show simple item record Arvind, V. Das, Bireswar Köbler, Johannes Kuhnert, Sebastian 2014-03-16T11:20:05Z 2014-03-16T11:20:05Z 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.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


My Account