Scheduling of a Smart Antenna: Capacitated Coloring of Unit Circular-Arc Graphs | Zendy

Guy Even | Zendy; Shimon Shahar | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Scheduling of a Smart Antenna: Capacitated Coloring of Unit Circular-Arc Graphs

Author(s) -

Guy Even,

Shimon Shahar

Publication year - 2006

Publication title -

lecture notes in computer science

Language(s) - English

Resource type - Book series

SCImago Journal Rank - 0.249

H-Index - 400

eISSN - 1611-3349

pISSN - 0302-9743

ISBN - 3-540-48822-7

DOI - 10.1007/11922377_6

Subject(s) - computer science , scheduling (production processes) , graph , graph coloring , mathematical optimization , schedule , combinatorics , theoretical computer science , mathematics , operating system

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.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research