A symmetry-breaking node equivalence for pruning the search space in backtracking algorithms

Čibej, Uroš (avtor), Fürst, Luka (avtor), Mihelič, Jurij (avtor)

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.

• Jezik: Angleški jezik
• Ključne besede: graph equivalence, symmetry breaking, backtracking, monomorphism search, search tree pruning, graph algorithm
• Vrsta gradiva: Članek v reviji
• Tipologija: 1.01 - Izvirni znanstveni članek
• Organizacija: FRI - Fakulteta za računalništvo in informatiko
• Status publikacije: Objavljeno
• Različica publikacije: Objavljena publikacija
• Leto izida: 2019
• Št. strani: 26 str.
• Številčenje: Vol. 11, iss. 10, art. 1300
• PID: 20.500.12556/RUL-133142
• UDK: 004:519.17
• ISSN pri članku: 2073-8994
• DOI: 10.3390/sym11101300
• COBISS.SI-ID: 1538408387
• Datum objave v RUL: 12.11.2021

Gradivo je del revije

• Naslov: Symmetry
• Skrajšan naslov: Symmetry
• Založnik: Molecular Diversity Preservation International
• ISSN: 2073-8994
• COBISS.SI-ID: 517592345

Licence

• Licenca: CC BY 4.0, Creative Commons Priznanje avtorstva 4.0 Mednarodna
• Povezava: http://creativecommons.org/licenses/by/4.0/deed.sl
• Opis: To je standardna licenca Creative Commons, ki daje uporabnikom največ možnosti za nadaljnjo uporabo dela, pri čemer morajo navesti avtorja.
• Začetek licenciranja: 15.10.2019

Sekundarni jezik

• Jezik: Slovenski jezik
• Ključne besede: grafna ekvivalenca, razbijanje simetrij, sestopanje, iskanje monomorfizmov, rezanje iskalnega drevesa, algoritem na grafih