GREEDY ALGORITHMS FOR OPTIMIZATION PROBLEMS ON UNIT INTERVAL GRAPHS

Abstract

In this paper, we show a very special property of unit interval graphs and use that property to introduce greedy algorithms for classical optimization problems on them: finding minimum dominating set, maximum independent set and maximum matching. These algorithms are all linear-time concerning the number of vertices of the graph and simple for implementation.