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

Povzetek

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.

Ključne besede

grafna ekvivalenca;razbijanje simetrij;sestopanje;iskanje monomorfizmov;rezanje iskalnega drevesa;algoritem na grafih;graph equivalence;symmetry breaking;backtracking;monomorphism search;search tree pruning;graph algorithm;

Podatki

Jezik: Angleški jezik
Leto izida:
Tipologija: 1.01 - Izvirni znanstveni članek
Organizacija: UL FRI - Fakulteta za računalništvo in informatiko
UDK: 004:519.17
COBISS: 1538408387 Povezava se bo odprla v novem oknu
ISSN: 2073-8994
Št. ogledov: 232
Št. prenosov: 44
Ocena: 0 (0 glasov)
Metapodatki: JSON JSON-RDF JSON-LD TURTLE N-TRIPLES XML RDFA MICRODATA DC-XML DC-RDF RDF

Ostali podatki

Sekundarni jezik: Slovenski jezik
Sekundarne ključne besede: grafna ekvivalenca;razbijanje simetrij;sestopanje;iskanje monomorfizmov;rezanje iskalnega drevesa;algoritem na grafih;
Vrsta dela (COBISS): Članek v reviji
Strani: str. 1-26
Letnik: ǂVol. ǂ11
Zvezek: ǂno. ǂ10
Čas izdaje: Oct. 2019
DOI: 10.3390/sym11101300
ID: 13925520