کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
426548 | 686104 | 2012 | 11 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: The isomorphism problem for k-trees is complete for logspace The isomorphism problem for k-trees is complete for logspace](/preview/png/426548.png)
We show that, for k constant, k -tree isomorphism can be decided in logarithmic space by giving an O(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 O((k+1)!n), where n is the number of vertices, yielding the fastest known FPT algorithm for k-tree isomorphism.
Journal: Information and Computation - Volume 217, August 2012, Pages 1–11