Priority algorithms for graph optimization problems

We continue the study of priority or “greedy-like ” algorithms as initiated in [10] and as extended to graph theoretic problems in [12]. Graph theoretic problems pose some modeling problems that did not exist in the original applications of [10] and [3]. Following [12], we further clarify these concepts. In the graph theoretic setting there are several natural input formulations for a given problem and we show that priority algorithm bounds in general depend on the input formulation. We study a variety of graph problems in the context of arbitrary and restricted priority models corresponding to known “greedy algorithms”