Better bounds for incremental frequency allocation in bipartite graphs

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F13%3A10190754" target="_blank" >RIV/00216208:11320/13:10190754 - isvavai.cz</a>
Alternative codes found
RIV/67985840:_____/13:00422569
Result on the web
<a href="http://dx.doi.org/10.1016/j.tcs.2012.05.020" target="_blank" >http://dx.doi.org/10.1016/j.tcs.2012.05.020</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1016/j.tcs.2012.05.020" target="_blank" >10.1016/j.tcs.2012.05.020</a>

Result language
angličtina
Original language name
Better bounds for incremental frequency allocation in bipartite graphs
Original language description
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 differentfrequency. 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. The offline version of the problem is known to be NP-hard. Inthe incremental version, requests for frequencies arrive over time and the algorithm is required to assign a frequency to a request as soon as it arrives. Competitive incremental algorithms have been studied for several classes of graphs. For paths, theoptimal (asymptotic) ratio is known to be 4/3, while for hexagonal-cell graphs it is between 1.5 and 1.9126. For xi-colorable graphs, the ratio of (xi + 1)/2 can be achieved. In this paper, we prove nearly tight bounds on the asymptotic c
Czech name
—
Czech description
—

Type
J<sub>x</sub> - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)
CEP classification
IN - Informatics
OECD FORD branch
—

Project
Result was created during the realization of more than one project. More information in the Projects tab.
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Publication year
2013
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Similar results(10)