On minimum path cover in interval graphs.

摘要

Graph searching is a fundamental technique used to visit the vertices of a graph. Recently, a technique where a search is repeated a small constant number of times using information gathered from previous searches has gained popularity. These multi-sweep search algorithms are simple to express and easy to implement.As an application to this technique we introduce a new kind of graph search called right-most neighbour. We define a hybrid-sweep algorithm which takes an order characterizing interval graphs and using right-most neighbour on this order, we produce a minimum path cover together with a certificate of optimality.The information used from previous sweeps is simply an ordering of the vertices. We generalize multi-sweep techniques to hybrid-sweep techniques whereby we grant more flexibility to the ordering given to the graph search. In particular, we allow the ordering to come from other kinds of searches or other structured orders of the vertices.