2006 | OriginalPaper | Buchkapitel
Scheduling of a Smart Antenna: Capacitated Coloring of Unit Circular-Arc Graphs
verfasst von : Guy Even, Shimon Shahar
Erschienen in: Combinatorial and Algorithmic Aspects of Networking
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We consider scheduling problems that are motivated by an optimization of the transmission schedule of a smart antenna. In these problems we are given a set of messages and a conflict graph that specifies which messages cannot be transmitted concurrently. In our model the conflict graph is a unit circular-arc graph.
Two variants of the problem are considered:
c-mbl
and
nu-c-mbl
. In
c-mbl
, the messages have unit demands, whereas in
nu-c-mbl
demands are arbitrary. We present an optimal algorithm for
c-mbl
and a 3-approximation algorithm for
nu-c-mbl
.