A Logspace Algorithm for Partial 2-Tree Canonization

DOI10.1007/978-3-540-79709-8_8zbMath1142.68368OpenAlexW1571206720MaRDI QIDQ3503623

Bireswar Das, V. Arvind, Johannes Köbler

Publication date: 5 June 2008

Published in: Computer Science – Theory and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-79709-8_8

Mathematics Subject Classification ID

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

Related Items

The Isomorphism Problem for k-Trees Is Complete for Logspace ⋮ A computational approach to construct a multivariate complete graph invariant ⋮ The isomorphism problem for planar 3-connected graphs is in unambiguous logspace ⋮ A note on integral generalized flows in directed partial 2-trees ⋮ Graphs of Bounded Treewidth Can Be Canonized in  $\mbox{{\sf AC}$^1$}$ ⋮ The isomorphism problem for \(k\)-trees is complete for logspace

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Linear time algorithms for NP-hard problems restricted to partial k- trees
• Group-theoretic algorithms and graph isomorphism
• Canonical representations of partial 2- and 3-trees
• Treewidth. Computations and approximations
• Completeness results for graph isomorphism.
• The isomorphism problem for planar 3-connected graphs is in unambiguous logspace
• Undirected ST-connectivity in log-space
• Testing Graph Isomorphism in Parallel by Playing a Game
• Random Graph Isomorphism
• Relationships among $PL$, $\#L$, and the determinant
• The Space Complexity of k-Tree Isomorphism
• On acyclic simplicial complexes