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

Autor:	Uroš Čibej, Luka Fürst, Jurij Mihelič
Jazyk:	angličtina
Rok vydání:	2019
Předmět:	graph equivalence symmetry breaking backtracking monomorphism search search tree pruning graph algorithm Mathematics QA1-939
Zdroj:	Symmetry, Vol 11, Iss 10, p 1300 (2019)
Druh dokumentu:	article
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:	Directory of Open Access Journals
Externí odkaz:	https://doaj.org/article/cd176d7b17244959845af944b446128d Zobrazit plný text záznamu View record in DOAJ Plný text ve formátu PDF Plný text ve formátu HTML
Nepřihlášeným uživatelům se plný text nezobrazuje	K zobrazení výsledku je třeba se přihlásit.