Testing Graph Isomorphism in Parallel by Playing a Game
From MaRDI portal
Publication:3613744
DOI10.1007/11786986_2zbMath1223.68056arXivcs/0603054MaRDI 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
68Q25: Analysis of algorithms and problem complexity
68W10: Parallel algorithms in computer science
05C85: Graph algorithms (graph-theoretic aspects)
03C13: Model theory of finite structures
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
68Q19: Descriptive complexity and finite models
Related Items
Unnamed Item, The Space Complexity of k-Tree Isomorphism, The isomorphism problem for \(k\)-trees is complete for logspace, Restricted space algorithms for isomorphism on bounded treewidth graphs, The isomorphism problem for planar 3-connected graphs is in unambiguous logspace, Graphs of Bounded Treewidth Can Be Canonized in $\mbox{{\sf AC}$^1$}$, A Logspace Algorithm for Partial 2-Tree Canonization, From Invariants to Canonization in Parallel, Fixed-Point Definability and Polynomial Time on Chordal Graphs and Line Graphs