Better bounds for incremental frequency allocation in bipartite graphs

0422569 - MÚ 2014 RIV NL eng J - Journal Article
Chrobak, M. - Jeż, Łukasz - Sgall, J.
Better bounds for incremental frequency allocation in bipartite graphs.
Theoretical Computer Science. Roč. 514, 25 November (2013), s. 75-83. ISSN 0304-3975. E-ISSN 1879-2294
R&D Projects: GA AV ČR IAA100190902; GA ČR GBP202/12/G061
Institutional support: RVO:67985840
Keywords : online algorithms * frequency allocation * graph algorithms
Subject RIV: BA - General Mathematics
Impact factor: 0.516, year: 2013
http://www.sciencedirect.com/science/article/pii/S0304397512004781

We study frequency allocation in wireless networks. A wireless network is modeled by an undirected graph, with vertices corresponding to cells. In each vertex, we have a certain number of requests, and each of those requests must be assigned a different frequency. Edges represent conflicts between cells, meaning that frequencies in adjacent vertices must be different as well. The objective is to minimize the total number of used frequencies.
Permanent Link: http://hdl.handle.net/11104/0228703