The complexity of modular graph automorphism

DOI10.1137/S0097539799358227MaRDI QIDQ2706110zbMATH OpenOpenAlexFDO

Authors Vikraman Arvind, Richard Beigel, Antoni Lozano

Publication date 19 March 2001

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/s0097539799358227

zbMATH Keywords

decision problemsgraph automorphismgraph isomorphismIP protocolsprogram checkingsearch problems

Mathematics Subject Classification ID

General theory for finite permutation groups (20B05) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Analysis of algorithms and problem complexity (68Q25) Parallel algorithms in computer science (68W10)

Recommendations

• scientific article; zbMATH DE number 1136076
• Computational complexity of computing a partial solution for the graph automorphism problems
• Descriptive complexity of modularity problems on graphs
• LATIN 2004: Theoretical Informatics
• The parameterised complexity of computing the maximum modularity of a graph
• scientific article; zbMATH DE number 7378595
• Graph automorphisms of a finite modular lattice
• An algebraic analysis of the graph modularity
• Computing graph automorphism from partial solutions
• Automorphic decompositions of graphs

Cited in

(7)

• Computational complexity of computing a partial solution for the graph automorphism problems
• Relating Complete and Partial Solution for Problems Similar to Graph Automorphism
• scientific article; zbMATH DE number 1136076 (Why is no real title available?)
• scientific article; zbMATH DE number 7378595 (Why is no real title available?)
• Applications of dimensionality reduction and exponential sums to graph automorphism
• A note on decision versus search for graph automorphism
• On the asymmetric complexity of the group-intersection problem

This page was built for publication: The complexity of modular graph automorphism

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2706110)