Vaš brskalnik ne omogoča JavaScript!
JavaScript je nujen za pravilno delovanje teh spletnih strani. Omogočite JavaScript ali pa uporabite sodobnejši brskalnik.
Nacionalni portal odprte znanosti
Odprta znanost
DiKUL
slv
|
eng
Iskanje
Brskanje
Novo v RUL
Kaj je RUL
V številkah
Pomoč
Prijava
A symmetry-breaking node equivalence for pruning the search space in backtracking algorithms
ID
Čibej, Uroš
(
Avtor
),
ID
Fürst, Luka
(
Avtor
),
ID
Mihelič, Jurij
(
Avtor
)
PDF - Predstavitvena datoteka,
prenos
(472,07 KB)
MD5: FFED25A616AB2716DD3E95754B512330
URL - Izvorni URL, za dostop obiščite
https://www.mdpi.com/2073-8994/11/10/1300
Galerija slik
Izvleček
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
Število ogledov:
1318
Število prenosov:
189
Metapodatki:
Citiraj gradivo
Navadno besedilo
BibTeX
EndNote XML
EndNote/Refer
RIS
ABNT
ACM Ref
AMA
APA
Chicago 17th Author-Date
Harvard
IEEE
ISO 690
MLA
Vancouver
:
Kopiraj citat
Objavi na:
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
Podobna dela
Podobna dela v RUL:
Podobna dela v drugih slovenskih zbirkah:
Nazaj