A generic framework for engineering graph canonization algorithms

Publikation: Bidrag til bog/antologi/rapport/konference-proceedingKonferencebidrag i proceedingsForskningpeer review

169 Downloads (Pure)

Abstrakt

The state-of-the-art tools for practical graph canonization are all based on the individualization-refinement paradigm, and their di erence is primarily in the choice of heuristics they include and in the actual tool implementation. It is thus not possible to make a direct comparison of how individual algorithmic ideas a ect the performance on di erent graph classes. We present an algorithmic software framework that facilitates implementation of heuristics as independent extensions to a common core algorithm. It therefore becomes easy to perform a detailed comparison of the performance and behaviour of di erent algorithmic ideas. Implementations are provided of a range of algorithms for tree traversal, target cell selection, and node invariant, including choices from the literature and new variations. The framework readily supports extraction and visualization of detailed data from separate algorithm executions for subsequent analysis and development of new heuristics. Using collections of di erent graph classes we investigate the e ect of varying the selections of heuristics, often revealing exactly which individual algorithmic choice is responsible for particularly good or bad performance. On several benchmark collections, including a newly proposed class of di cult instances, we additionally find that our implementation performs better than the current state-of-the-art tools.

OriginalsprogEngelsk
Titel2018 Proceedings of the 20th Workshop on Algorithm Engineering and Experiments, ALENEX 2018
RedaktørerSuresh Venkatasubramanian, Rasmus Pagh
ForlagSociety for Industrial and Applied Mathematics Publications
Publikationsdatojan. 2018
Sider139-153
ISBN (Elektronisk)978-1-61197-505-5
DOI
StatusUdgivet - jan. 2018
Begivenhed20th Workshop on Algorithm Engineering and Experiments, ALENEX 2018 - New Orleans, USA
Varighed: 7. jan. 20188. jan. 2018

Konference

Konference20th Workshop on Algorithm Engineering and Experiments, ALENEX 2018
LandUSA
ByNew Orleans
Periode07/01/201808/01/2018

    Fingerprint

Citationsformater

Andersen, J. L., & Merkle, D. (2018). A generic framework for engineering graph canonization algorithms. I S. Venkatasubramanian, & R. Pagh (red.), 2018 Proceedings of the 20th Workshop on Algorithm Engineering and Experiments, ALENEX 2018 (s. 139-153). Society for Industrial and Applied Mathematics Publications. https://doi.org/10.1137/1.9781611975055.13