The parallel complexity of graph canonization under abelian group action

DOI10.1007/s00453-013-9805-0zbMath1277.68082MaRDI QIDQ378219

V. Arvind, Johannes Köbler

Publication date: 11 November 2013

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-013-9805-0

zbMATH Keywords

parallel complexity; graph isomorphism; logspace counting classes

Mathematics Subject Classification ID

05C65: Hypergraphs

05C15: Coloring of graphs and hypergraphs

05C78: Graph labelling (graceful graphs, bandwidth, etc.)

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)

05C60: Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Isomorphism and canonization of tournaments and hypertournaments
• Parallel algorithms for solvable permutation groups
• Completeness results for graph isomorphism.
• The complexity of matrix rank and feasible systems of linear equations
• Undirected ST-connectivity in log-space
• A taxonomy of problems with fast parallel algorithms
• The Parallel Complexity of Abelian Permutation Group Problems
• Parallel Tree Contraction Part 2: Further Applications
• Structure and importance of logspace-MOD class
• On the Hardness of Graph Isomorphism
• Relationships among $PL$, $\#L$, and the determinant
• On Hypergraph and Graph Isomorphism with Bounded Color Classes
• STACS 2005