Article ID Journal Published Year Pages File Type
1141621 Discrete Optimization 2006 9 Pages PDF
Abstract

We consider the problem of finding a minimum cost cycle in a digraph with real-valued costs on the vertices. This problem generalizes the problem of finding a longest cycle and hence is NP-hard for general digraphs. We prove that the problem is solvable in polynomial time for extended semicomplete digraphs and for quasi-transitive digraphs, thereby generalizing a number of previous results on these classes. As a byproduct of our method we develop polynomial algorithms for the following problem: Given a quasi-transitive digraph DD with real-valued vertex costs, find, for each j=1,2,…,|V(D)|j=1,2,…,|V(D)|, jj disjoint paths P1,P2,…,PjP1,P2,…,Pj such that the total cost of these paths is minimum among all collections of jj disjoint paths in DD.

Related Topics
Physical Sciences and Engineering Mathematics Control and Optimization
Authors
, , ,