20.500.12556/RUL-133142 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 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. graph equivalence symmetry breaking backtracking monomorphism search search tree pruning graph algorithm grafna ekvivalenca razbijanje simetrij sestopanje iskanje monomorfizmov rezanje iskalnega drevesa algoritem na grafih true false true Angleški jezik Slovenski jezik Članek v reviji 2021-11-12 15:14:11 2021-11-12 15:14:12 2022-09-12 04:15:04 0000-00-00 00:00:00 2019 0 0 26 str. iss. 10, art. 1300 Vol. 11 Oct. 2019 0000-00-00 Zaloznikova Objavljeno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 004:519.17 2073-8994 10.3390/sym11101300 1538408387 RAZ_Cibej_Uros_2019.pdf RAZ_Cibej_Uros_2019.pdf 1 FFED25A616AB2716DD3E95754B512330 0192564e40f1b365dddf47f0d2fa518f9dc48f12d3c49c359ed93dea5f8361c1 13fc01a1-43c3-11ec-abdb-00155dcfd717 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=150982 https://www.mdpi.com/2073-8994/11/10/1300 1 bfd87711-43c2-11ec-abdb-00155dcfd717 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=150981 Fakulteta za računalništvo in informatiko 0 0 0