Models and approximation algorithms for channel assignment in radio networks

被引：91

作者：

Krumke, SO

Marathe, MV

Ravi, SS

机构：

[1] Konrad Zuse Zentrum Informat Tech Berlin, D-14195 Berlin, Germany

[2] Los Alamos Natl Lab, Los Alamos, NM 87545 USA

[3] SUNY Albany, Dept Comp Sci, Albany, NY 12222 USA

来源：

WIRELESS NETWORKS | 2001年 / 7卷 / 06期

基金：

美国国家科学基金会;

关键词：

channel assignment; radio networks; approximation algorithms; geometric graphs;

D O I：

10.1023/A:1012311216333

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

We consider the frequency assignment (broadcast scheduling) problem for packet radio networks. Such networks are naturally modeled by graphs with a certain geometric structure. The problem of broadcast scheduling can be cast as a variant of the vertex coloring problem (called the distance-2 coloring problem) on the graph that models a given packet radio network, We present efficient approximation algorithms for the distance-2 coloring problem for various geometric graphs including those that naturally model a large class of packet radio networks. The class of graphs considered include (r, s)-civilized graphs, planar graphs, graphs with bounded genus, etc.

引用

页码：575 / 584

页数：10

共 33 条

[1]

Agnarsson G, 2000, PROCEEDINGS OF THE ELEVENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, P654

[2] LINEAR TIME ALGORITHMS FOR NP-HARD PROBLEMS RESTRICTED TO PARTIAL K-TREES [J].