Parallel Computation of Combinatorial Symmetries.
From MaRDI portal
Abstract: In practice symmetries of combinatorial structures are computed by transforming the structure into an annotated graph whose automorphisms correspond exactly to the desired symmetries. An automorphism solver is then employed to compute the automorphism group of the constructed graph. Such solvers have been developed for over 50 years, and highly efficient sequential, single core tools are available. However no competitive parallel tools are available for the task. We introduce a new parallel randomized algorithm that is based on a modification of the individualization-refinement paradigm used by sequential solvers. The use of randomization crucially enables parallelization. We report extensive benchmark results that show that our solver is competitive to state-of-the-art solvers on a single thread, while scaling remarkably well with the use of more threads. This results in order-of-magnitude improvements on many graph classes over state-of-the-art solvers. In fact, our tool is the first parallel graph automorphism tool that outperforms current sequential tools.
Cited in
(8)- scientific article; zbMATH DE number 4047161 (Why is no real title available?)
- Detecting and handling reflection symmetries in mixed-integer (nonlinear) programming and beyond
- Satsuma: structure-based symmetry breaking in SAT
- Group graphs and computational symmetry on massively parallel architecture
- Parallel computation of invariant measures
- Computational complexity of the Weisfeiler-Leman dimension
- Computational complexity of the Weisfeiler-Leman dimension
- Random sampling of contingency tables and partitions: two practical examples of the Burnside process
This page was built for publication: Parallel Computation of Combinatorial Symmetries.
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6052040)
