首页 | 本学科首页   官方微博 | 高级检索  
     


Three results on frequency assignment in linear cellular networks
Authors:Marek Chrobak  Ji?í Sgall
Affiliation:a Department of Computer Science, University of California, Riverside, CA 92521, USA
b Department of Applied Mathematics, Faculty of Mathematics and Physics, Charles University, Malostranské nám. 25, CZ-11800 Praha 1, Czech Republic
Abstract:In the frequency assignment problem we are given a graph representing a wireless network and a sequence of requests, where each request is associated with a vertex. Each request has two more attributes: its arrival and departure times, and it is considered active from the time of arrival to the time of departure. We want to assign frequencies to all requests so that at each time step any two active requests associated with the same or adjacent vertices use different frequencies. The objective is to minimize the number of frequencies used.We focus exclusively on the special case of the problem when the underlying graph is a linear network (path). For this case, we consider both the offline and online versions of the problem, and we present three results. First, in the incremental online case, where the requests arrive over time, but never depart, we give an algorithm with an optimal (asymptotic) competitive ratio View the MathML source. Second, in the general online case, where the requests arrive and depart over time, we improve the current lower bound on the (asymptotic) competitive ratio to View the MathML source. Third, we prove that the offline version of this problem is NP-complete.
Keywords:Frequency assignment  Cellular networks  Online algorithms  Competitive analysis  _method=retrieve&  _eid=1-s2  0-S0304397509006574&  _mathId=si4  gif&  _pii=S0304397509006574&  _issn=03043975&  _acct=C000069490&  _version=1&  _userid=6211566&  md5=aac30b18e80820545ffeedb92cc40a02')" style="cursor:pointer  NP-completeness" target="_blank">" alt="Click to view the MathML source" title="Click to view the MathML source">NP-completeness
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号