language: en

Vertex heaviest paths and cycles in quasi-transitive digraphs

Jtrgen Bang-Jensen Gregory Gutin
Department of Mathematics and Computer Science Odense University,
Denmark

Abstract A digraph D is called a quasi-transitive digraph (QTD) if for any triple x; ; of distinct vertices of D such that (x; ) and (; ) are arcs of D there is at least one arc from x to or from to x. Solving a conjecture by J. Bang-Jensen and J. Huang (J. Graph Theory, to appear), G. Gutin (Australas. J. Combin., to appear) described polynomial algorithms for finding a Hamiltonian cycle and a Hamiltonian path (if it exists) in a QTD. The approach taken in that paper cannot be used to find a longest path or cycle in polynomial time. We present a principally new approach that leads to polynomial algorithms for finding vertex heaviest paths and cycles in QTD's with non-negative weights on the vertices. This, in particular, provides an answer to a question by N. Alon on longest paths and cycles in QTD's.

1 Introduction