2-local distributed algorithms for generalized coloring of hexagonal graphs

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

Abstract

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.

Keywords

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;

Data

Language:	English
Year of publishing:	2005
Typology:	1.08 - Published Scientific Conference Contribution
Organization:	UM FS - Faculty of Mechanical Engineering
UDC:	519.174
COBISS:	13826393
ISSN:	1571-0653
Views:	53
Downloads:	37
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	Slovenian
Secondary title:	2-lokalen porazdeljeni algoritmi za posplošeno barvanje heksagonalnih grafov
Secondary keywords:	matematika;teorija grafov;barvanje grafov;aproksimacijski algoritem;frekvenčni načrt;▫$k$▫-lokalen porazdeljen algoritem;
URN:	URN:SI:UM:
Type (COBISS):	Not categorized
Pages:	str. 321-325
Issue:	ǂVol. ǂ22
Chronology:	2005
ID:	1472589