SEMICOMPLETE MULTIPARTITE DIGRAPHS AND THE TRAVELING SALESMAN PROBLEM
Dr Anders Yeo, Department of Computer Science, University of Aarhus, Denmark

Abstract: In this talk I will discuss results from the two main areas of my research. Namely algorithmic and structural results on paths and cycles in semicomplete multipartite digraphs and results on the traveling salesman problem.

A semicomplete multipartite digraph (SMD) is a digraph, D, whose vertex set can be partitioned into sets V1,V2,...,Vp such that any two vertices from different sets have an arc between them, and any two vertices from the same set have no arc between them. I will outline the proof of the result that every regular (i.e. every vertex has equally many arcs into it and out of it) SMD has a Hamiltonian cycle (i.e. a cycle containing all vertices). This proved a well-known conjecture by C.Q.Chang. I will furthermore give some generalizations of this result. Finally I will mention a few algorithmic results, such as the Hamilton cycle problem is polynomially time solvable for SMD's, which also proves a well-known conjecture.

The second part of the talk will concern the traveling salesman problem (TSP), which is one of the best known problems in graph theory and combinatorial optimization. The TSP is the problem of finding a Hamilton cycle (also called a tour) of minimum cost in a complete digraph, with weights on its arcs. As the TSP is an NP-hard problem, we are unlikely to find a polynomial time algorithm for it. A recent development is to try and find solutions in polynomial time, which can be guaranteed to be at least as good as a large number of other solutions. One then hopes that the more solutions we can guarantee it will be at least as good as, the better the algorithm will work. I will present a number of results in this area, including the most recent results showing that one can find, in polynomial time, a solution that is at least as good as half of all solutions (i.e. least as good as (n-1)!/2 solutions). This result is based on a, so far, unpublished result by Haggkvist. I will also present some results based only on published results, which furthermore perform well in practice!

This seminar was held at the Department of Computer Science, Royal Holloway, University of London on 12 September 2000.

back