Gregory Gutin and Bang-Jensen, J. (1996) Vertex heaviest paths and cycles in quasi-transitive digraphs.. Discrete Mathematics, 163 (1-3).
Full text access: Open
A digraph D is called a quasi-transitive digraph (QTD) if for any triple x,y,z of distinct vertices of D such that (x, y) and (y, z) are arcs of D there is at least one arc from x and z or from z to x. Solving a conjecture by Bang-Jensen and Huang (1995), Gutin (1995) 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 QTDs 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 QTDs.
This is a Published version This version's date is: 1996 This item is not peer reviewed
https://repository.royalholloway.ac.uk/items/da197cd9-1b99-ab50-bbc7-39be8b91a3d8/1/
Deposited by () on 23-Dec-2009 in Royal Holloway Research Online.Last modified on 25-May-2010