zbMATH — the first resource for mathematics

A logspace algorithm for partial 2-tree canonization. (English) Zbl 1142.68368
Hirsch, Edward A. (ed.) et al., Computer science – theory and applications. Third international computer science symposium in Russia, CSR 2008 Moscow, Russia, June 7–12, 2008. Proceedings. Berlin: Springer (ISBN 978-3-540-79708-1/pbk). Lecture Notes in Computer Science 5010, 40-51 (2008).
Summary: We show that partial 2-tree canonization, and hence isomorphism testing for partial 2-trees, is in deterministic logspace. Our algorithm involves two steps: (a) We exploit the “tree of cycles” property of biconnected partial 2-trees to canonize them in logspace. (b) We analyze Lindell’s tree canonization algorithm and show that canonizing general partial 2-trees is also in logspace, using the algorithm to canonize biconnected partial 2-trees.
For the entire collection see [Zbl 1136.68005].

68Q25 Analysis of algorithms and problem complexity
05C05 Trees
05C85 Graph algorithms (graph-theoretic aspects)
Full Text: DOI