Models and Approximation Algorithms for Channel Assignment in Radio Networks
Lists
Only you see this
Abstract
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.
BibTeX
@inproceedings{krumke2001models,
author = {Sven Oliver Krumke and Madhav V. Marathe and S. S. Ravi},
title = {{Models and Approximation Algorithms for Channel Assignment in Radio Networks}},
booktitle = {Wirel. Networks},
year = {2001},
url = {https://openreview.net/forum?id=0wUZh1eHO7G},
}Loading related content...