A note on finding minimum mean cycle

被引：7

作者：

Chaturvedi, Mmanu ^{[1
]}

McConnell, Ross M. ^{[1
]}

机构：

[1] Colorado State Univ, Dept Comp Sci, Ft Collins, CO 80523 USA

来源：

INFORMATION PROCESSING LETTERS | 2017年 / 127卷

关键词：

Analysis of algorithms; Design of algorithms; Graph algorithms;

D O I：

10.1016/j.ipl.2017.06.007

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

In a directed graph with edge weights, the mean weight of a directed cycle is the weight of its edges divided by their number. The minimum cycle mean of the graph is the minimum mean weight of a cycle. Karp gave a characterization of minimum cycle mean and an O(nm) algorithm to compute it, where n is the number of vertices and m is the number of edges. However, an algorithm he suggested for identifying a cycle with this mean weight is not correct. We propose an alternative. (C) 2017 Elsevier B.V. All rights reserved.

引用

页码：21 / 22

页数：2