Graph Symmetry Detection and Canonical Labeling: Differences and Synergies
From MaRDI portal
Publication:6235331
arXiv1208.6271MaRDI QIDQ6235331FDOQ6235331
Hadi Katebi, Karem A. Sakallah, Igor L. Markov
Publication date: 30 August 2012
Abstract: Symmetries of combinatorial objects are known to complicate search algorithms, but such obstacles can often be removed by detecting symmetries early and discarding symmetric subproblems. Canonical labeling of combinatorial objects facilitates easy equivalence checking through quick matching. All existing canonical labeling software also finds symmetries, but the fastest symmetry-finding software does not perform canonical labeling. In this work, we contrast the two problems and dissect typical algorithms to identify their similarities and differences. We then develop a novel approach to canonical labeling where symmetries are found first and then used to speed up the canonical labeling algorithms. Empirical results show that this approach outperforms state-of-the-art canonical labelers.
This page was built for publication: Graph Symmetry Detection and Canonical Labeling: Differences and Synergies
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6235331)
