A Symmetry-Breaking Node Equivalence for Pruning the Search Space in Backtracking Algorithms

We introduce a new equivalence on graphs, defined by its symmetry-breaking capability. We first present a framework for various backtracking search algorithms, in which the equivalence is used to prune the search tree. Subsequently, we define the equivalence and an optimization problem with the goal...

Full description

Bibliographic Details
Main Authors: Uroš Čibej, Luka Fürst, Jurij Mihelič
Format: Article
Language:English
Published: MDPI AG 2019-10-01
Series:Symmetry
Subjects:
Online Access:https://www.mdpi.com/2073-8994/11/10/1300