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

Autor: Luka Fürst, Jurij Mihelič, Uros Cibej
Jazyk: angličtina
Rok vydání: 2019
Předmět:
Optimization problem
iskanje monomorfizmov
Physics and Astronomy (miscellaneous)
Computer science
General Mathematics
Backtracking
0102 computer and information sciences
02 engineering and technology
symmetry breaking
01 natural sciences
Monomorphism search
search tree pruning
razbijanje simetrij
backtracking
udc:004:519.17
graph equivalence
graph algorithm
0202 electrical engineering
electronic engineering
information engineering
Computer Science (miscellaneous)
Graph algorithms
Symmetry breaking
Equivalence (formal languages)
grafna ekvivalenca
business.industry
lcsh:Mathematics
Graph algorithm
Usability
lcsh:QA1-939
Search tree
sestopanje
rezanje iskalnega drevesa
TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES
010201 computation theory & mathematics
Chemistry (miscellaneous)
Computer Science::Programming Languages
Graph equivalence
monomorphism search
020201 artificial intelligence & image processing
Search tree pruning
business
Algorithm
algoritem na grafih
Zdroj: Symmetry
Volume 11
Issue 10
Symmetry, Vol 11, Iss 10, p 1300 (2019)
Symmetry, vol. 11, no. 10, 1300, 2019.
ISSN: 2073-8994
DOI: 10.3390/sym11101300
Popis: 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 of finding an equivalence partition with the highest pruning potential. We also position the optimization problem into the computational-complexity hierarchy. In particular, we show that the verifier lies between P and NP -complete problems. Striving for a practical usability of the approach, we devise a heuristic method for general graphs and optimal algorithms for trees and cycles.
Databáze: OpenAIRE
Externí odkaz:
Nepřihlášeným uživatelům se plný text nezobrazuje