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



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


  1. Let G be a directed graph with real-valued edge weights and two distinguished vertices, s and t. Describe an efficient algorithm to find a path from s to t whose minimum edge weight is maximum. Prove the correctness of your algorithm and analyze its running time. A minimally acceptable solution is time; there is a way to do it in time. To obtain the latter, think about using median-finding in combination with an incremental search process.)


    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