On-line Algorithms for Mobile Computing
Paul Spirakis
We present work concerning algorithmic issues for Mobile Computing.
Specifically , we discuss :
- The problem of on-line allocation
of frequencies to mobile stations . We present various results for
the competitive ratio wrt optimal off-line allocation. The results
are stated with the help of the notion of the interference graph
among fixed stations. For the greedy method we show a tight result
for the competitive ratio , namely that is the reverse of the maximum
degree of the interference network. For planar interference networks
we show a constant ratio. For general networks and request patterns
that may access every station we show a competitive ratio essentially
the reverse of the average degree.
- The problem of mobile antiviruus software hunting a mobile
eavesdropper. We show that even two mobile antivirus modules are enough
to eliminate the bug in small polynomial time , even for the case where
the bug has unlimited memory.
- We define the radiochromatic number of a graph , motivated by the
frequency interference problem. We show its determination eequivalent
to TSP of 1 and 2 distances and we show various ressults about the
on-line radiochromatic coloring of a graph.
This is joint work with T Pantziou , D Fotakis , B Tampakas and
G Pentaris.