A Logspace Algorithm for Partial 2-Tree Canonization
From MaRDI portal
Publication:3503623
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
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
