| | 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.
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 v DKUM: 31.03.2017; Ogledov: 493; Prenosov: 69
.pdf Celotno besedilo (142,13 KB)
Gradivo ima več datotek! Več...

2.
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 v DKUM: 10.07.2015; Ogledov: 825; Prenosov: 20
URL Povezava na celotno besedilo

3.
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 v DKUM: 10.07.2015; Ogledov: 829; Prenosov: 83
URL Povezava na celotno besedilo

5.
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 v DKUM: 10.07.2015; Ogledov: 793; Prenosov: 70
URL Povezava na celotno besedilo

6.
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 v DKUM: 10.07.2015; Ogledov: 1360; Prenosov: 91
URL Povezava na celotno besedilo

7.
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 v DKUM: 10.07.2015; Ogledov: 884; Prenosov: 29
URL Povezava na celotno besedilo

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