Creative Commons Attribution 4.0 license (CC BY 4.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2021.24
URN: urn:nbn:de:0030-drops-154578
URL: https://drops.dagstuhl.de/opus/volltexte/2021/15457/
Anders, Markus ; Brachter, Jendrik ; Schweitzer, Pascal
A Characterization of Individualization-Refinement Trees
| pdf-format: |
|
Abstract
Individualization-Refinement (IR) algorithms form the standard method and currently the only practical method for symmetry computations of graphs and combinatorial objects in general. Through backtracking, on each graph an IR-algorithm implicitly creates an IR-tree whose order is the determining factor of the running time of the algorithm.We give a precise and constructive characterization which trees are IR-trees. This characterization is applicable both when the tree is regarded as an uncolored object but also when regarded as a colored object where vertex colors stem from a node invariant. We also provide a construction that given a tree produces a corresponding graph whenever possible. This provides a constructive proof that our necessary conditions are also sufficient for the characterization.
BibTeX - Entry
@InProceedings{anders_et_al:LIPIcs.ISAAC.2021.24,
author = {Anders, Markus and Brachter, Jendrik and Schweitzer, Pascal},
title = {{A Characterization of Individualization-Refinement Trees}},
booktitle = {32nd International Symposium on Algorithms and Computation (ISAAC 2021)},
pages = {24:1--24:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-214-3},
ISSN = {1868-8969},
year = {2021},
volume = {212},
editor = {Ahn, Hee-Kap and Sadakane, Kunihiko},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/15457},
URN = {urn:nbn:de:0030-drops-154578},
doi = {10.4230/LIPIcs.ISAAC.2021.24},
annote = {Keywords: individualization refinement algorithms, backtracking trees, graph isomorphism}
}
| Keywords: | individualization refinement algorithms, backtracking trees, graph isomorphism | |
| Seminar: | 32nd International Symposium on Algorithms and Computation (ISAAC 2021) | |
| Issue date: | 2021 | |
| Date of publication: | 30.11.2021 |
