An O( n 2 ) algorithm for the maximum cycle mean of an n x n bivalent matrix

作者: P. Butkovic , R.A. Cuninghame-Green

DOI: 10.1016/0166-218X(92)90039-D

关键词:

摘要: Abstract For a general n × real matrix ( ij ), standard O( 3 ) algorithms exist to find its maximum cycle mean, i.e., λ A )= max i 1 2 + k l )\ over all cyclic permutations ,…, of subsets the set {1,2,…, }. We consider case when elements take values in binary { a,b } and construct an algorithm complexity which then suffices λ( ).

参考文章(6)
George B. Dantzig, W. O. Blattner, M. R. Rao, FINDING A CYCLE IN A GRAPH WITH MINIMUM COST TO TIME RATIO WITH APPLICATION TO A SHIP ROUTING PROBLEM Defense Technical Information Center. ,(1966) , 10.21236/AD0646553
Peter Butkovič, Ján Plávka, On the dependence of the maximum cycle mean of a matrix on permutations of the rows and columns Discrete Applied Mathematics. ,vol. 23, pp. 45- 53 ,(1989) , 10.1016/0166-218X(89)90034-6
Richard M. Karp, A characterization of the minimum cycle mean in a digraph Discrete Mathematics. ,vol. 23, pp. 309- 311 ,(1978) , 10.1016/0012-365X(78)90011-0
R. A. Cuninghame-Green, Describing Industrial Processes with Interference and Approximating Their Steady-State Behaviour Journal of the Operational Research Society. ,vol. 13, pp. 95- 100 ,(1962) , 10.1057/JORS.1962.10
Eugene L. Lawler, Combinatorial optimization : networks and matroids Dover Publications. ,(1976)