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...
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 |
Similar Items
-
SEARCH-TREE SIZE ESTIMATION FOR THE SUBGRAPH ISOMORPHISM PROBLEM
by: Uroš Čibej, et al.
Published: (2019-01-01) -
Graph Coloring via Clique Search with Symmetry Breaking
by: Sándor Szabó, et al.
Published: (2022-07-01) -
Developing Backtracking Algorithm to Find the Optimal Solution Path
by: Suhad M. Kadhum, et al.
Published: (2010-12-01) -
SVD++ Recommendation Algorithm Based on Backtracking
by: Shijie Wang, et al.
Published: (2020-07-01) -
Symmetries and symmetry-breaking in arithmetic graphs
by: Aqsa Shah, et al.
Published: (2023-09-01)