(Logo)   IMADA
University of Southern Denmark IMADA - Department of Mathematics and Computer Science
   

COMPUTER SCIENCE COLLOQUIUM

PhD colloqium: Quasi-Hamiltonian Paths in Semicomplete Multipartite Digraphs

Sven Simonsen
Department of Mathematics and Computer Science
University of Southern Denmark, Denmark

Tuesday, 30 October, 2012 at 14:15
IMADA's Seminar Room

ABSTRACT

A quasi-hamiltonian path in a semicomplete multipartite digraph D is a path which visits each maximal independent set (also called a partite set) of D at least once. This is a generalization of hamiltonian paths in tournaments.

In this talk we will investigate the complexity of finding a quasi-hamiltonian path starting in x and terminating in y as well as the complexity of finding a quasi-hamiltonian path starting in either x or y and terminating in the other vertex. We consider both of these problems for the class of semicomplete multipartite digraphs. While both problems are polynomially solvable for semicomplete digraphs (here all maximal independent sets have size one), we prove that the first problem is actually NP-complete for semicomplete multipartite digraphs. We then describe a polynomial algorithm for the latter problem in SMDs.

Host:

SDU HOME | IMADA HOME | Previous Page
Daniel Merkle