Povzetek
Ena glavnih nalog planiranja celičnih omrežij je dodeljevanje frekvenc oddajnikom, znotraj omejenega frekvenčnega spektra, pri danih frekvenčnih omejitvah. Celično omrežje je običajno predstavljeno kot podgraf neskončne trikotniške mreže oziroma heksagonalen graf. Nalogo dodeljevanja frekvenc lahko obravnavamo kot nalogo večbarvanja uteženih heksagonalnih grafov, kjer uteži predstavljajo število klicev, ki morajo biti dodeljeni posamezni celici. V članku predstavimo porazdeljen algoritem za večbarvanje heksagonalnih grafov, pri čemer za vsako točko ▫$v$▫ danega grafa ▫$G$▫ uporabimo le lokalni klični števili ▫$\omega_{1}(v)$▫ in ▫$\omega_{2}(v)$▫. Pokažemo, da za večbarvanje poljubnega heksagonalnega grafa ▫$G$▫ algoritem potrebuje kvečjemu ▫$\lceil 4\omega(G)/3 \rceil$▫ barv, ne da bi dejansko izračunal globalno klično število ▫$\omega(G)$▫. Pokažemo tudi, da je algoritem 2-lokalen.
Ključne besede
matematika;teorija grafov;barvanje grafov;frekvenčni načrt;celična omrežja;2-lokalen porazdeljen algoritem;mathematics;graph theory;graph coloring;2-local distributed algorithm;cellular networks;frequency planning;
Podatki
Jezik: |
Angleški jezik |
Leto izida: |
2005 |
Tipologija: |
1.01 - Izvirni znanstveni članek |
Organizacija: |
UM FS - Fakulteta za strojništvo |
UDK: |
519.17 |
COBISS: |
9538582
|
ISSN: |
0196-6774 |
Št. ogledov: |
1737 |
Št. prenosov: |
82 |
Ocena: |
0 (0 glasov) |
Metapodatki: |
|
Ostali podatki
Sekundarni jezik: |
Angleški jezik |
Sekundarni naslov: |
2-lokalni 4/3-aproksimacijski algoritem za večbarvanje heksagonalnih grafov |
Sekundarni povzetek: |
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 as a 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 the vertex. We prove the algorithm uses no more than ▫$\lceil 4\omega(G)/3 \rceil$▫ 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. |
Sekundarne ključne besede: |
matematika;teorija grafov;barvanje grafov;algoritem; |
URN: |
URN:SI:UM: |
Strani: |
str. 29-41 |
Letnik: |
ǂVol. ǂ55 |
Zvezek: |
ǂiss. ǂ1 |
Čas izdaje: |
2005 |
ID: |
8718290 |