Cos 423 Problem Set No. 5-revised Due Wed. April 23, 2003 Spring 2003



Download 0.51 Mb.
Page3/6
Date02.05.2018
Size0.51 Mb.
#47335
1   2   3   4   5   6




  1. (See CLRS Problem 24-5, page 617.) Let G=(V,E) be a strongly connected directed graph with real-valued edge weightfor each edge e. A minimum mean-weight cycle is a cycle that minimizes the sum of edge weights divided by the number of edges. Prove the correctness of the following algorithm to compute a minimum mean-weight cycle, and show how to implement it to run in time.


    Download 0.51 Mb.

    Share with your friends:
1   2   3   4   5   6




The database is protected by copyright ©ininet.org 2024
send message

    Main page