| | SLO | ENG | Cookies and privacy

Bigger font | Smaller font

Search the digital library catalog Help

Query: search in
search in
search in
search in
* old and bologna study programme

Options:
  Reset


1 - 7 / 7
First pagePrevious page1Next pageLast page
1.
How good can ants color graphs?
Aleksander Vesel, Janez Žerovnik, 1998

Abstract: V notici primerjamo algoritem Coste in Hertza, algoritem "mravlje", s postopkom zaporednega barvanja (RLF, recursive largest first) in z algoritmom tipa Petforf-Welsh. V naših poskusih je zadnji precej boljši od prvih dveh.
Keywords: matematika, teorija grafov, barvanje grafov, postopek zaporednega barvanja, algoritem mravlje, Petford-Welsh, RLF, mathematics, graph theory, graph coloring, ants algorithm, Petford-Welsh, RLF
Published: 10.07.2015; Views: 541; Downloads: 21
URL Link to full text

2.
Memetic self-adaptive firefly algorithm
Iztok Fister, Xin-She Yang, Janez Brest, Iztok Fister, 2013, independent scientific component part or a chapter in a monograph

Keywords: firefly algorithms, memetic algorithms, self-adaptation, local search, graph 3-coloring problem
Published: 10.07.2015; Views: 965; Downloads: 79
URL Link to full text

3.
Simpler multicoloring of triangle-free hexagonal graphs
Ignasi Sau Walls, Petra Šparl, Janez Žerovnik, 2012, published scientific conference contribution

Abstract: Preslikavo ▫$f colon V(G)to 2^{{1,.,n}}$▫, za katero velja ▫$|f(v)| ge p(v)$▫ za vsako točko ▫$v in V(G)$▫ in ▫$f(v) cap f(u) = emptyset$▫ za poljubni sosedi ▫$u$▫ in ▫$v$▫ grafa ▫$G$▫, imenujemo dobro ▫$n-[p]$▫barvanje grafa ▫$G$▫. Najmanjše naravno število, za katero obstaja dobro ▫$n-[p]$▫barvanje grafa ▫$G$▫, ▫$chi_p(G)$▫, imenujemo uteženo kromatično število grafa ▫$G$▫. Iskanje uteženega kromatičnega števila za inducirane podgrafe trikotniške mreže (imenovane heksagonalni grafi) ima aplikacije v celičnih mrežah. Uteženo kromatično število grafa ▫$G$▫, ▫$omega_p(G)$▫, je enako maksimalni uteži klike grafa ▫$G$▫, kjer utež klike predstavlja vsoto uteži njenih točk. McDiarmid in Reed (2000) sta postavila domnevo, da za poljuben heksagonalen graf brez trikotnikov velja ▫$chi_p(G) le (9/8)omega_p(G) + C$▫. V članku je podan algoritem, ki poda dobro ▫$7-[3]$▫barvanje poljubnega heksagonalnega grafa brez trikotnikov, ki aplicira neenakost ▫$chi_p(G) le (7/6)omega_p(G) + C$▫. Naš rezultat podaja krajšo alternativo induktivnega dokaza Haveta (2001) in izboljša kratek dokaz Sudepa in Vishwanathana (2005), ki sta dokazala obstoj ▫$14-[6]$▫barvanja. (Omeniti je potrebno, da v sklopu našega dokaza uporabimo izrek o štirih barvah.) Vsi koraki algoritma so linearni glede na ▫$|V(G)|$▫, razen 4-barvanje ravninskega grafa. Novi pristop lahko v prihodnje pripomore k dokazovanju domneve McDiarmida in Reeda (2000).
Keywords: matematika, teorija grafov, aproksimacijski algoritem, barvanje grafov, dodeljevanje frekvenc, celične mreže, mathematics, graph algorithm, graph theory, approximation algorithm, graph coloring, frequency planning, cellular networks
Published: 10.07.2015; Views: 537; Downloads: 57
URL Link to full text

4.
2-local distributed algorithms for generalized coloring of hexagonal graphs
Petra Šparl, Janez Žerovnik, 2005, published scientific conference contribution

Abstract: A 2-local distributed approximation algorithm for multicoloring of a triangle-free hexagonal graph which uses at most ▫$lceil frac{5omega(G)}{4} rceil + 3$▫ colors is presented.
Keywords: matematika, teorija grafov, barvanje grafov, aproksimacijski algoritem, frekvenčni načrt, ▫$k$▫-lokalen porazdeljen algoritem, mathematics, graph theory, approximation algorithms, graph coloring, frequency planning, ▫$k$▫-local distributed algorithm
Published: 10.07.2015; Views: 623; Downloads: 69
URL Link to full text

5.
6.
Explicit homomorphisms of hexagonal graphs to one vertex deleted Petersen graph
Petra Šparl, Janez Žerovnik, 2009, original scientific article

Abstract: Problem odločanja ali obstaja homomorfizem iz poljubnega grafa ▫$G$▫ v dani graf ▫$H$▫ je bil že večkrat proučevan in se je izkazal za zelo težkega. Hell in Nešetril sta dokazala, da je odločitveni problem NP-poln, če ▫$H$▫ ni dvodelen graf. V članku je obravnavan poseben problem, kjer je ▫$G$▫ poljuben heksagonalen graf brez trikotnikov, ▫$H$▫ pa Kneserjev graf ali njegov inducirani podgraf. Podana je esplicitna konstrukcija, ki dokazuje obstoj homomorfizma iz poljubnega heksagonalnega grafa brez trikotnikov v Petersenov graf brez ene točke.
Keywords: matematika, teorija grafov, homomorfizem, H-barvanje, heksagonalen graf brez trikotnikov, mathematics, teorija grafov, homomorphism, H-coloring, triangle-free hexagonal graph
Published: 10.07.2015; Views: 504; Downloads: 15
URL Link to full text

7.
On acyclic colorings of direct products
Simon Špacapan, Aleksandra Tepeh, 2008, original scientific article

Abstract: A coloring of a graph ▫$G$▫ is an acyclic coloring if the union of any two color classes induces a forest. It is proved that the acyclic chromatic number of direct product of two trees ▫$T_1$▫ and ▫$T_2$▫ equals ▫$\min\{ \Delta(T_1) + 1, \Delta(T_2) + 1\}$▫. We also prove that the acyclic chromatic number of direct product of two complete graphs ▫$K_m$▫ and ▫$K_n$▫ is ▫$mn-m-2$▫, where ▫$m \ge n \ge 4$▫. Several bounds for the acyclic chromatic number of direct products are given and in connection to this some questions are raised.
Keywords: mathematics, graph theory, coloring, acyclic coloring, distance-two coloring, direct product
Published: 31.03.2017; Views: 287; Downloads: 54
.pdf Full text (142,13 KB)
This document has many files! More...

Search done in 0.17 sec.
Back to top
Logos of partners University of Maribor University of Ljubljana University of Primorska University of Nova Gorica