Greedy algorithms for generalized k-rankings of paths

A k  -ranking of a graph is a labeling of the vertices with positive integers 1,2,…,k1,2,…,k so that every path connecting two vertices with the same label contains a vertex of larger label. An optimal ranking is one in which k   is minimized. Let PnPn be a path with n vertices. A greedy algorithm can be used to successively label each vertex with the smallest possible label that preserves the ranking property. We seek to show that when a greedy algorithm is used to label the vertices successively from left to right, we obtain an optimal ranking. A greedy algorithm of this type was given by Bodlaender et al. in 1998 [1] which generates an optimal k  -ranking of PnPn. In this paper we investigate two generalizations of rankings. We first consider bounded (k,s)(k,s)-rankings in which the number of times a label can be used is bounded by a predetermined integer s  . We then consider ktkt-rankings where any path connecting two vertices with the same label contains t vertices with larger labels. We show for both generalizations that when G is a path, the analogous greedy algorithms generate optimal k  -rankings. We then proceed to quantify the minimum number of labels that can be used in these rankings. We define the bounded rank number (G)r,s to be the smallest number of labels that can be used in a (k,s)(k,s)-ranking and show for n⩾2n⩾2, (Pn)r,s=⌈((n−(2i−1))/s)⌉+i where i=⌊log2(s)⌋+1i=⌊log2(s)⌋+1. We define the ktkt-rank number, (G)rt to be the smallest number of labels that can be used in a ktkt-ranking. We present a recursive formula that gives the ktkt-rank numbers for paths, showing (Pj)rt=n for all an−1

Research highlights
► Two generalizations of rankings are presented.
► Optimal labelings are constructed for each generalization.
► Greedy algorithms are identified that produce optimal solutions.