2-local distributed algorithms for generalized coloring of hexagonal graphs

Petra Šparl (Avtor), Janez Žerovnik (Avtor)

Povzetek

A 2-local distributed approximation algorithm for multicoloring of a triangle-free hexagonal graph which uses at most ▫$\lceil \frac{5\omega(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;

Podatki

Jezik:	Angleški jezik
Leto izida:	2005
Tipologija:	1.08 - Objavljeni znanstveni prispevek na konferenci
Organizacija:	UM FS - Fakulteta za strojništvo
UDK:	519.174
COBISS:	13826393
ISSN:	1571-0653
Št. ogledov:	53
Št. prenosov:	37
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Slovenski jezik
Sekundarni naslov:	2-lokalen porazdeljeni algoritmi za posplošeno barvanje heksagonalnih grafov
Sekundarne ključne besede:	matematika;teorija grafov;barvanje grafov;aproksimacijski algoritem;frekvenčni načrt;▫$k$▫-lokalen porazdeljen algoritem;
URN:	URN:SI:UM:
Vrsta dela (COBISS):	Delo ni kategorizirano
Strani:	str. 321-325
Zvezek:	ǂVol. ǂ22
Čas izdaje:	2005
ID:	1472589