Testing Graph Isomorphism in Parallel by Playing a Game
From MaRDI portal
Publication:3613744
DOI10.1007/11786986_2zbMath1223.68056arXivcs/0603054OpenAlexW1658031827MaRDI QIDQ3613744
Publication date: 12 March 2009
Published in: Automata, Languages and Programming (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/cs/0603054
Analysis of algorithms and problem complexity (68Q25) Parallel algorithms in computer science (68W10) Graph algorithms (graph-theoretic aspects) (05C85) Model theory of finite structures (03C13) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Descriptive complexity and finite models (68Q19)
Related Items (11)
A Logspace Algorithm for Partial 2-Tree Canonization ⋮ From Invariants to Canonization in Parallel ⋮ Unnamed Item ⋮ The isomorphism problem for planar 3-connected graphs is in unambiguous logspace ⋮ The Space Complexity of k-Tree Isomorphism ⋮ Graphs of Bounded Treewidth Can Be Canonized in $\mbox{{\sf AC}$^1$}$ ⋮ Distributed Testing of Graph Isomorphism in the CONGEST Model. ⋮ Fixed-Point Definability and Polynomial Time on Chordal Graphs and Line Graphs ⋮ Unnamed Item ⋮ The isomorphism problem for \(k\)-trees is complete for logspace ⋮ Restricted space algorithms for isomorphism on bounded treewidth graphs
This page was built for publication: Testing Graph Isomorphism in Parallel by Playing a Game
