| | 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 - 10 / 19
First pagePrevious page12Next pageLast page
1.
2-local 3/4-competitive algorithm for multicoloring hexagonal graphs
Petra Šparl, Janez Žerovnik, 2005, original scientific article

Abstract: An important optimization problem in the design of cellular networks is to assign sets of frequencies to transmitters to avoid unacceptable interference.A cellular network is generally modeled as a subgraph of the infinite triangular lattice. Frequency assignment problem can be abstracted asa multicoloring problem on a weighted hexagonal graph, where the weights represent the number of calls to be assigned at vertices. In this paper we present a distributed algorithm for multicoloring hexagonal graphs using only the local clique numbers ▫$omega_1(v)$▫ and ▫$omega_2(v)$▫ at each vertex v of the given hexagonal graph, which can be computed from local information available at thevertex. We prove the algorithm uses no more than ▫$4omega(G)/3$▫ colors for any hexagonal graph G, without explicitly computing the global clique number ▫$omega(G)$▫. We also prove that our algorithm is 2-local, i.e., the computation at a vertex v ▫$in$▫ G uses only information about the demands of vertices whose graph distance from v is less than or equal to 2.
Keywords: mathematics, graph theory, graph colouring, 2-local distributed algorithm, cellular networks, frequency planning
Published: 01.06.2012; Views: 1323; Downloads: 61
URL Link to full text

2.
3.
Embedding of complete and nearly complete binary trees into hypercubes
Aleksander Vesel, 2011, published scientific conference contribution

Abstract: A new simple algorithm for optimal embedding of complete binary trees into hypercubes as well as a node-by-node algorithm for embedding of nearly complete binary trees into hypercubes are presented.
Keywords: mathematics, graph theory, embedding, binary trees, algorithm
Published: 07.06.2012; Views: 932; Downloads: 19
URL Link to full text

4.
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: 421; Downloads: 17
URL Link to full text

5.
Embedding of complete and nearly complete binary trees into hypercubes
Aleksander Vesel, 2010

Abstract: A new simple algorithm for optimal embedding of complete binary trees into hypercubes as well as a node-by-node algorithm for embedding of nearly complete binary trees into hypercubes are presented.
Keywords: matematika, teorija grafov, vložitev, hiperkocka, algoritem, mathematics, graph theory, embedding, complete binary tree, hypercube, algorithm
Published: 10.07.2015; Views: 318; Downloads: 12
URL Link to full text

6.
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: 423; Downloads: 50
URL Link to full text

7.
8.
On the canonical metric representation, average distance, and partial Hamming graphs
Sandi Klavžar, 2006, original scientific article

Abstract: Povprečna razdalja grafa je izražena s pomočjo kanonične metrične reprezentacije. Enakost lahko preoblikujemo v neenakost tako, da karakterizira izometrične podgrafe Hammingovih grafov. Ta pristop poenostavlja prepoznavanje teh grafov ter izračun povprečne razdalje.
Keywords: matematika, teorija grafov, kanonična metrična reprezentacija, Hammingovi grafi, delni Hammingovi grafi, Wienerjev indeks, algoritem prepoznavanja, mathematics, graph theory, cononical metric representation, Hamming graphs, partial Hamming graphs, Wiener index, recognition algorithm
Published: 10.07.2015; Views: 440; Downloads: 57
URL Link to full text

9.
Algorithm for recognizing Cartesian graph bundles
Blaž Zmazek, Janez Žerovnik, 1999, published scientific conference contribution abstract

Abstract: Grafovski svežnji predstavljajo posplošitev krovnih in produktnih grafov. V članku vpeljemo enolično lokalno produktno relacijo ▫$Delta$▫ na kartezičnih svežnjih nad baznimi grafi, ki ne vsebujejo grafa ▫$K_4 setminus e$▫ in podamo algoritem za razpoznavanje kartezičnih svežnjev nad enostavnimi baznimi grafi brez ▫$K_4 setminus e$▫.
Keywords: matematika, teorija grafov, kartezični grafovski svežnji, enolična lokalna produktna lastnost, osnovna faktorizacija, razpoznavanje, polinomski algoritem, mathematics, graph theory, Cartesian graph bundles, unique square property, fundamental factorization, polynomial algorithm, recognition
Published: 10.07.2015; Views: 361; Downloads: 53
URL Link to full text

10.
The obnoxious center problem on weighted cactus graphs
Blaž Zmazek, Janez Žerovnik, 2001, published scientific conference contribution abstract

Abstract: Problem nezaželenih centrov v grafu predstavlja določitev takšne lokacije na povezavah grafa, da je njena minimalna razdalja do poljubne točke grafa kolikor se da velika. Uteži na točkah grafa lahko predstavljajo njihovo občutljivost, ki jo je moč oceniti z eno izmed konstantno mnogo vrednosti. Kadar je vsaki točki grafa prirejena ena izmed ▫$c$▫ različnih vrednosti (uteži) glede na njeno občutljivost, rešujemo tako imenovan problem nezaželenih centrov na grafu z ovrednotenimi točkami. V tem članku bomo predstavili algoritem, ki določi nezaželeni center na kaktusu z ovrednotenimi točkami v linearnem času ▫$O(cn)$▫, kjer je ▫$n$▫ število točk in ▫$c$▫ število uteži.
Keywords: matematika, operacijsko raziskovanje, teorija grafov, lokacijski problemi, problem centra, nezaželjeni centri, algoritmi z linearno časovno zahtevnostjo, mathematics, operations research, graph theory, location problems, center problem, obnoxious facilities, linear time algorithm
Published: 10.07.2015; Views: 476; Downloads: 57
URL Link to full text

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