The Space Complexity of k-Tree Isomorphism

2007/12/06 by V. Arvind, Bireswar Das, Johannes Köbler · 6 citations
Chemistry · Computer Science · Mathematics · #Advanced Graph Theory Research #Algorithms and Data Compression #Artificial intelligence #Chemistry #Class (philosophy) #Combinatorics #Complexity and Algorithms in Graphs #Computer science #Crystal structure #Crystallography #Discrete mathematics #Isomorphism (crystallography) #Mathematics #Oracle #Space (punctuation) #Tree (set theory)

paper · doi:10.1007/978-3-540-77120-3_71

published in Lecture Notes in Computer Science, 822-833 (Springer Berlin Heidelberg)

openalex publication_date 2007/12/06 · crossref created 2007/12/06 · crossref deposited 2021/04/27 · crossref indexed 2024/09/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/04

Citations

• Canonical labeling of graphs
• Isomorphism of graphs of bounded valence can be tested in polynomial time
• Linear time algorithms for NP-hard problems restricted to partial k-trees
• Dynamic programming on graphs with bounded treewidth
• Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees
• Graduate Texts in Mathematics

Cited by

• A Logspace Algorithm for Partial 2-Tree Canonization
• Graph canonization [wikipedia]