| | SLO | ENG | Piškotki in zasebnost

Večja pisava | Manjša pisava

Iskanje po katalogu digitalne knjižnice Pomoč

Iskalni niz: išči po
išči po
išči po
išči po
* po starem in bolonjskem študiju

Opcije:
  Ponastavi


1 - 7 / 7
Na začetekNa prejšnjo stran1Na naslednjo stranNa konec
1.
How good can ants color graphs?
Aleksander Vesel, Janez Žerovnik, 1998

Opis: 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.
Ključne besede: matematika, teorija grafov, barvanje grafov, postopek zaporednega barvanja, algoritem mravlje, Petford-Welsh, RLF, mathematics, graph theory, graph coloring, ants algorithm, Petford-Welsh, RLF
Objavljeno: 10.07.2015; Ogledov: 358; Prenosov: 17
URL Povezava na celotno besedilo

2.
Memetic self-adaptive firefly algorithm
Iztok Fister, Xin-She Yang, Janez Brest, Iztok Fister, 2013, samostojni znanstveni sestavek ali poglavje v monografski publikaciji

Ključne besede: firefly algorithms, memetic algorithms, self-adaptation, local search, graph 3-coloring problem
Objavljeno: 10.07.2015; Ogledov: 704; Prenosov: 61
URL Povezava na celotno besedilo

3.
Simpler multicoloring of triangle-free hexagonal graphs
Ignasi Sau Walls, Petra Šparl, Janez Žerovnik, 2012, objavljeni znanstveni prispevek na konferenci

Opis: 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).
Ključne besede: 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
Objavljeno: 10.07.2015; Ogledov: 369; Prenosov: 41
URL Povezava na celotno besedilo

4.
2-local distributed algorithms for generalized coloring of hexagonal graphs
Petra Šparl, Janez Žerovnik, 2005, objavljeni znanstveni prispevek na konferenci

Opis: 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.
Ključne besede: 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
Objavljeno: 10.07.2015; Ogledov: 458; Prenosov: 53
URL Povezava na celotno besedilo

5.
6.
Explicit homomorphisms of hexagonal graphs to one vertex deleted Petersen graph
Petra Šparl, Janez Žerovnik, 2009, izvirni znanstveni članek

Opis: 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.
Ključne besede: matematika, teorija grafov, homomorfizem, H-barvanje, heksagonalen graf brez trikotnikov, mathematics, teorija grafov, homomorphism, H-coloring, triangle-free hexagonal graph
Objavljeno: 10.07.2015; Ogledov: 359; Prenosov: 8
URL Povezava na celotno besedilo

7.
On acyclic colorings of direct products
Simon Špacapan, Aleksandra Tepeh, 2008, izvirni znanstveni članek

Opis: 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.
Ključne besede: mathematics, graph theory, coloring, acyclic coloring, distance-two coloring, direct product
Objavljeno: 31.03.2017; Ogledov: 207; Prenosov: 38
.pdf Celotno besedilo (142,13 KB)
Gradivo ima več datotek! Več...

Iskanje izvedeno v 0.2 sek.
Na vrh
Logotipi partnerjev Univerza v Mariboru Univerza v Ljubljani Univerza na Primorskem Univerza v Novi Gorici