On-line Ranking Algorithms for Trees.
Chia‐Wei Lee, Justie Su-Tzu Juan · FCS · 2005
A node k-ranking of a graph G = (V, E) is a proper node coloring C: V {1, 2, ..., k} such that any path in G with end nodes x, y fulfilling C(x) = C(y) contains an internal node z with C(z) C(x). In the on-line version of this problem, the nodes v1, v2,..., vn are coming one by one in an arbitrary order; and only the edges of the induced subgraph G[{v1, v2, ..., vi}] are known when the color of vi has to be chosen. This paper gives an on-line ranking algorithm for general trees and an optimal on-line ranking algorithm for the special trees, K1,n, also called stars.