On-line ranking of split graphs
Piotr Borowiecki, Dariusz Dereniowski
Abstract
A vertex ranking of a graph G is an assignment of
positive integers (colors) to the vertices of G such that
each path connecting two vertices of the same color contains a vertex
of a higher color. Our main goal is to find a vertex ranking using as
few colors as possible. Considering on-line algorithms for vertex
ranking of split graphs, we prove that the worst case ratio of the
number of colors used by any on-line ranking algorithm and the number
of colors used in an optimal off-line solution may be arbitrarily
large. This negative result motivates us to investigate semi on-line
algorithms, where a split graph is presented on-line but its clique
number is given in advance. We prove that there does not exist a
(2-ɛ)-competitive semi on-line algorithm of this
type. Finally, a 2-competitive semi on-line algorithm is
given.
Full Text: PDF PostScript