Name
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. |
Year | DOI | Venue |
|---|---|---|
2001 | 10.1023/A:1012311216333 | Wireless Networks |
Keywords | Field | DocType |
channel assignment,radio networks,approximation algorithms,geometric graphs | Complete coloring,Discrete mathematics,Indifference graph,Mathematical optimization,Computer science,Chordal graph,Computer network,Greedy coloring,Pathwidth,Longest path problem,Maximal independent set,Graph coloring | Journal |
Volume | Issue | ISSN |
7 | 6 | 1572-8196 |
Citations | PageRank | References |
96 | 7.54 | 22 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Sven O. Krumke | 1 | 308 | 36.62 |
| Madhav Marathe | 2 | 2775 | 262.17 |
| S. S. Ravi | 3 | 2259 | 227.21 |