The parallel complexity of graph canonization under abelian group action

DOI10.1007/s00453-013-9805-0zbMath1277.68082OpenAlexW2089433923MaRDI 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 complexitygraph isomorphismlogspace counting classes

Mathematics Subject Classification ID

Hypergraphs (05C65) Coloring of graphs and hypergraphs (05C15) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

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

This page was built for publication: The parallel complexity of graph canonization under abelian group action