On-Line Algorithms for Vertex-Rankings of Graphs

A vertex-ranking of a graph G is a labeling of the vertices of G such that every path between two vertices with the same label gamma contains a vertex with label lambda > gamma. In any on-line vertex-ranking algorithm, the vertices arrive one at a time in any order and only the local information in the vertices of the induced subgraph G[{nu₁.....nu_i}] is available when the algorithm must choose a rank for Vi. The best known online algorithm for vertex-ranking a tree takes O(n³) time, where n is the number of vertices in the tree. In this paper we present an O(n²) time on-line algorithm for ranking the vertices of a tree. We also derive an upper bound on the number of ranks used by the algorithm for an important sub-class of trees, namely complete t-ary trees. Finally we provide an on-line vertex ranking algorithm for simple graphs by extending the on-line tree ranking algorithm.