The Space Complexity of k-Tree Isomorphism

DOI10.1007/978-3-540-77120-3_71MaRDI QIDQ5387816zbMATH OpenOpenAlexFDO

Authors Vikraman Arvind, Bireswar Das, Johannes Köbler

Publication date 27 May 2008

Published in Algorithms and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-77120-3_71

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• On the complexity of finding iso- and other morphisms for partial \(k\)- trees
• The complexity of subgraph isomorphism for classes of partial k-trees
• Restricted space algorithms for isomorphism on bounded treewidth graphs
• Restricted space algorithms for isomorphism on bounded treewidth graphs
• The Isomorphism Problem for k-Trees Is Complete for Logspace
• The isomorphism problem for \(k\)-trees is complete for logspace
• Complexity of tree homomorphisms
• Isomorphic tree spanner problems
• scientific article; zbMATH DE number 1335884
• Complexity of Finding Embeddings in a k-Tree

Cites work

• A combinatorial and logical approach to linear-time computability (extended abstract)
• Bounded Tree-Width and LOGCFL
• Completeness results for graph isomorphism.
• Embeddings of \(k\)-connected graphs of pathwidth \(k\)
• Fast parallel reordering and isomorphism testing of \(k\)-trees
• scientific article; zbMATH DE number 4060712 (Why is no real title available?)
• scientific article; zbMATH DE number 1256777 (Why is no real title available?)
• scientific article; zbMATH DE number 1346519 (Why is no real title available?)
• scientific article; zbMATH DE number 1025912 (Why is no real title available?)
• scientific article; zbMATH DE number 1088188 (Why is no real title available?)
• scientific article; zbMATH DE number 1091108 (Why is no real title available?)
• scientific article; zbMATH DE number 2196509 (Why is no real title available?)
• Isomorphism of graphs of bounded valence can be tested in polynomial time
• Isomorphism of k-contractible graphs. A generalization of bounded valence and bounded genus
• Isomorphism Testing in Hookup Classes
• Isomorphism testing of k-trees is in NC, for fixed k
• Linear time algorithms for NP-hard problems restricted to partial k- trees
• NC algorithms for recognizing chordal graphs and k trees
• Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees
• Relationships among $PL$, $\#L$, and the determinant
• RUSPACE\((\log n)\subseteq \text{DSPACE}(\log^2n/\log \log n)\)
• Testing Graph Isomorphism in Parallel by Playing a Game
• Treewidth. Computations and approximations

Cited in

(10)

• The Isomorphism Problem for k-Trees Is Complete for Logspace
• scientific article; zbMATH DE number 3866594 (Why is no real title available?)
• A Logspace Algorithm for Partial 2-Tree Canonization
• Log-space algorithms for paths and matchings in k-trees
• scientific article; zbMATH DE number 1335884 (Why is no real title available?)
• The isomorphism problem for \(k\)-trees is complete for logspace
• Representing simplicial complexes with mangroves
• A linear time and space algorithm for finding isomorphic subtrees of a binary tree
• A computational approach to construct a multivariate complete graph invariant
• Isomorphism testing of k-trees is in NC, for fixed k

This page was built for publication: The Space Complexity of k-Tree Isomorphism

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5387816)