Better bounds for incremental frequency allocation in bipartite graphs

Kód výsledku v 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>

Nalezeny alternativní kódy

RIV/67985840:_____/13:00422569

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

Better bounds for incremental frequency allocation in bipartite graphs

Popis výsledku v původním jazyce

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

Název v anglickém jazyce

Better bounds for incremental frequency allocation in bipartite graphs

Popis výsledku anglicky

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

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

CEP obor

IN - Informatika

OECD FORD obor

—

Projekt

Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2013

Kód důvěrnosti údajů

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

Název periodika

Theoretical Computer Science

ISSN

0304-3975

e-ISSN

—

Svazek periodika

514

Číslo periodika v rámci svazku

November

Stát vydavatele periodika

NL - Nizozemsko

Počet stran výsledku

9

Strana od-do

75-83

Kód UT WoS článku

000329014000006

EID výsledku v databázi Scopus

—