Opened 13 years ago

Last modified 12 years ago

## #413 new enhancement

# Implement Young-Tarjan-Orlin algorithm for min mean cycle

Reported by: | Peter Kovacs | Owned by: | Alpar Juttner |
---|---|---|---|

Priority: | major | Milestone: | |

Component: | core | Version: | hg main |

Keywords: | Cc: | ||

Revision id: |

### Description

It would be nice to implement the Young-Tarjan-Orlin algorithm for the minimum mean cycle problem.

According to several survey papers, it is one of the fastest solution methods for this problem (and its extension: the optimum cycle ratio problem). Another method that is highly efficient is Howard's algorithm, which is already implemented in LEMON.

### Change History (4)

### comment:1 Changed 13 years ago by

Type: | task → enhancement |
---|

### comment:2 Changed 13 years ago by

Here is a citation for the Y-T-O algorithm:

- N. Young, R.E. Tarjan, and J.B. Orlin. Faster Parametric Shortest Path and Minimum Balance Algorithms. Networks, 21:205–221, 1991.

And here are some good survey papers on the topic:

- L. Georgiadis, A.V. Goldberg, R.E. Tarjan, and R.F. Werneck, An Experimental Study of Minimum Mean Cycle Algorithms, in Proc. 6th International Workshop on Algorithm Engineering and Experiments, SIAM, 2009.
- A. Dasdan. Experimental Analysis of the Fastest Optimum Cycle Ratio and Mean Algorithms. ACM Transactions on Design Automation of Electronic Systems, 9(4):385–418, 2004.
- A. Dasdan, S. Irani, and R. K. Gupta. Efficient Algorithms for Optimum Cycle Mean and Optimum Cost to Time Ratio Problem. In Proceedings of the 36th Design Automation Conference, 1999.

### comment:4 Changed 12 years ago by

Summary: | Young-Tarjan-Orlin algorithm for min mean cycle → Implement Young-Tarjan-Orlin algorithm for min mean cycle |
---|

**Note:**See TracTickets for help on using tickets.

Could you give a citation to this method?

For the record, could you give the theoretical running time of Young-Tarjan-Orlin?