| | SLO | ENG | Piškotki in zasebnost

Večja pisava | Manjša pisava

Izpis gradiva

Naslov:2-local 3/4-competitive algorithm for multicoloring hexagonal graphs
Avtorji:Šparl, Petra (Avtor)
Žerovnik, Janez (Avtor)
Datoteke:URL http://dx.doi.org/10.1016/j.jalgor.2004.09.001
 
Jezik:Angleški jezik
Vrsta gradiva:Neznano ()
Tipologija:1.01 - Izvirni znanstveni članek
Organizacija:FGPA - Fakulteta za gradbeništvo, prometno inženirstvo in arhitekturo
Opis: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.
Ključne besede:mathematics, graph theory, graph colouring, 2-local distributed algorithm, cellular networks, frequency planning
Leto izida:2005
UDK:519.17
COBISS_ID:9538582 Povezava se odpre v novem oknu
ISSN pri članku:0196-6774
NUK URN:URN:SI:UM:DK:BV6K7TAP
Število ogledov:1237
Število prenosov:51
Metapodatki:XML RDF-CHPDL DC-XML DC-RDF
Področja:Ostalo
:
  
Skupna ocena:(0 glasov)
Vaša ocena:Ocenjevanje je dovoljeno samo prijavljenim uporabnikom.
Objavi na:AddThis
AddThis uporablja piškotke, za katere potrebujemo vaše privoljenje.
Uredi privoljenje...

Postavite miškin kazalec na naslov za izpis povzetka. Klik na naslov izpiše podrobnosti ali sproži prenos.

Gradivo je del revije

Naslov:Journal of algorithms
Skrajšan naslov:J. algorithms
Založnik:Academic Press.
ISSN:0196-6774
COBISS.SI-ID:25704704 Novo okno

Sekundarni jezik

Jezik:Angleški jezik
Ključne besede:matematika, teorija grafov, barvanje grafov, algoritem


Komentarji

Dodaj komentar

Za komentiranje se morate prijaviti.

Komentarji (0)
0 - 0 / 0
 
Ni komentarjev!

Nazaj
Logotipi partnerjev Univerza v Mariboru Univerza v Ljubljani Univerza na Primorskem Univerza v Novi Gorici