1_Faster_Maximum_Mean_Cycle_Algorithms英文学习资料.pdf

Faster Maximum Mean Cycle Algorithms 1 Abstract We show that Karps algorithm pro cesses more vertices and arcs than needed to nd the maximum cycle mean of a digraph This observation motivated us to prop ose a new scheme called unfolding that remedies this deciency and leads to two algorithms Both asymptotic analysis and exp eriments on b enchmark graphs show that our algorithms run faster than Karps algorithm Like Karps algorithm they are applicable to b oth the maximum and minimum mean cycle problems 1 This pap er is pro duced using the IEEE transactions style le IEEEtransty with the draft option Octob er DRAFT I Introduction The average weight of a directed cycle is the total weight of the arcs on the cycle divided by the total numb er of the arcs on the cycle and is called the cycle mean The maximum mean cycle problem for a directed graph digraph with cycles is to nd a cycle having the maximum average weight called the maximum cycle mean over all directed cycles in the graph The minimum mean cycle problem and the minimum cycle mean are dened analogously Both of these problems have many imp ortant applications For instance some of the uses in p erformance analysis are as follows The minimum mean cycle problem has applications in nding the cycle p erio d in an asynchronous system and in dataow partitioning of synchronous systems the maximum mean cycle problem has applications in nding the iteration