Faster Canonical Forms for Primitive Coherent Configurations

DOI10.1145/2746539.2746617zbMath1321.05164arXiv1510.02195OpenAlexW1972761585MaRDI QIDQ2941564

Xiaorui Sun, John Wilmes

Publication date: 21 August 2015

Published in: Proceedings of the forty-seventh annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1510.02195

zbMATH Keywords

complexityalgorithmsassociation schemesstrongly regular graphsgraph isomorphismprimitive coherent configurations

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Association schemes, strongly regular graphs (05E30) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Coloring of graphs and hypergraphs (05C15) Directed graphs (digraphs), tournaments (05C20) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Multiply transitive finite groups (20B20)

Related Items (10)

Asymptotic Delsarte cliques in distance-regular graphs ⋮ Asymmetric coloring of locally finite graphs and profinite permutation groups: Tucker's conjecture confirmed ⋮ On the automorphism groups of rank-4 primitive coherent configurations ⋮ Most primitive groups are full automorphism groups of edge-transitive hypergraphs. ⋮ On the automorphism groups of strongly regular graphs. II. ⋮ Faster isomorphism for \(p\)-groups of class 2 and exponent \(p\) ⋮ On short expressions for cosets of permutation subgroups ⋮ The Weisfeiler-Leman algorithm and the diameter of Schreier graphs ⋮ Asymptotic enumeration of Cayley digraphs ⋮ Distance-regular graphs without 4-claws

Uses Software

• Graphs

Cites Work

• Unnamed Item
• Ramsey partitions and proximity data structures
• On sparse spanners of weighted graphs
• Scale-oblivious metric fragmentation and the nonlinear Dvoretzky theorem
• On Approximate Distance Labels and Routing Schemes with Affine Stretch
• Distance Oracles for Unweighted Graphs: Breaking the Quadratic Barrier with Constant Additive Error
• Approximate distance oracles
• Fast Algorithms for Constructing t-Spanners and Paths with Stretch t
• Near-Linear Time Construction of Sparse Neighborhood Covers
• Shortest-path queries in static networks
• Approximate distance oracles with constant query time
• Automata, Languages and Programming

This page was built for publication: Faster Canonical Forms for Primitive Coherent Configurations