Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1007/978-3-540-79709-8_8 | CSR |
Keywords | Field | DocType |
logspace algorithm,isomorphism testing,2-tree canonization,partial 2-trees,deterministic logspace,general partial 2-trees,tree canonization algorithm | Discrete mathematics,Combinatorics,Tree representation,Graph isomorphism,Algorithm,Isomorphism,Mathematics | Conference |
Volume | ISSN | ISBN |
5010 | 0302-9743 | 3-540-79708-4 |
Citations | PageRank | References |
12 | 0.66 | 14 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Vikraman Arvind | 1 | 296 | 38.18 |
| Bireswar Das | 2 | 66 | 10.61 |
| Johannes Köbler | 3 | 580 | 46.51 |