| | SLO | ENG | Cookies and privacy

Bigger font | Smaller font

# Show document

Title: 2-local 3/4-competitive algorithm for multicoloring hexagonal graphs Šparl, Petra (Author)Žerovnik, Janez (Author) http://dx.doi.org/10.1016/j.jalgor.2004.09.001 English Unknown () 1.01 - Original Scientific Article FGPA - Faculty of Civil Engineering, Transportation Engineering and Architecture 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. mathematics, graph theory, graph colouring, 2-local distributed algorithm, cellular networks, frequency planning 2005 519.17 0196-6774 9538582 URN:SI:UM:DK:BV6K7TAP 1294 58 Misc.

Hover the mouse pointer over a document title to show the abstract or click on the title to get all document metadata.

## Record is a part of a journal

Title: Journal of algorithms J. algorithms Academic Press. 0196-6774 25704704

## Secondary language

Language: English matematika, teorija grafov, barvanje grafov, algoritem

Leave comment