SEECS Colloquium

We survey results on hamiltonian paths and cycles in digraphs that are structurally related to tournaments. This includes well studied classes of digraphs such as extended semicomplete digraphs, quasi-transitive digraphs and locally semicomplete digraphs (all of which contain tournaments as a subclass) and the class of bipartite tournaments (these do not contain tournaments but are related through the common superclass of multipartite tournaments.

We will discuss the complexity of the hamiltonian path and cycle problems for these classes of digraphs. It turns out that for all the classes above the problems are polynomially solvable but the range of difficulty varies very much from the easiest (almost trivial) case of tournaments to the hardest (very complicated) case of multipartite tournaments.

We will also discuss parallellization of some of the algorithms above for the classes of extended semicomplete digraphs and bipartite tournaments. It turns out that quite a number of tricks are needed in order to obtain (R)NC algorithms for these problems which are closely related to the matching problem in bipartite graphs.

Joergen Bang-Jensen obtained his Ph.D in Computer science in 1988 from Odense University and is now an associate professor at University of Southern Denmark (the former Odense University). He is one of the authors of the book "Digraphs: Theory, Algorithms and Applications", J, Bang-Jensen and G. Gutin, Springer Verlag 2000, 754pp. and the author of more than 65 research publications on Graph theory and Graph algorithms. J.Bang-Jensen is currently visiting University of Victoria, British Columbia on his sabbatical.