On minimum path cover in interval graphs.
Published: 2007
Language: eng
Number of pages: 82
ISBN-13: 9780494272848
Description: 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.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.
Notes: Advisor: Derek Corneil.

Source: Masters Abstracts International, Volume: 45-06, page: 3184.

Thesis (M.Sc.)--University of Toronto, 2007.

Electronic version licensed for access by U. of T. users.

ROBARTS MICROTEXT copy on microfiche.