Math $315$ Network Flow Project Due: Thursday. $25$ April $2024$

Select one of the following projects. You may work with one other fellow student and submit a

collaborative project. In that case, indicate your partner$$s name in your submission.

$1.$ Compare and contrast the labelling methods of Ford and Fulkerson for the maximum flow

problem and of Dijkstra for the shortest distance. Explain clearly how they are similar, and

how they differ and illustrate with an example. So as to more easily compare the methods, use

a moderately complicated network in which the flow capacities for the maximal flow problem

are the same as the distances for the shortest distance problem.

$2.$ Pick an international location, which is not a major destination so is not the hub for any

airline. Determine the cheapest route $($one$-$way fares only$)$ to fly from Milwaukee to this

location. To get to this location, there must be at least $3$ stopovers enroute $($preferably

more$)$ and several different routes available. Be sure to draw the capacitated network as well

as identifying the cheapest route. Also provide evidence of the fares for each segment. As

an added exploration, you might determine the route of the shortest travel time, including

waiting between flights.

$3.$ Identify any other application of network flows, describe the application, and illustrate it with

an example.

$4.$ The course web page on canvas has the following papers available in the module $$Homework$.$

$$ On the history of the transportation and maximum flow problems $(2002)$

$$ The Pseudoflow Algorithm: A New Algorithm for the Maximum$-$Flow Problem $(2008)$

$$ Fast Shortest Path Distance Estimation in Large Networks $(2009)$

$$ Mapping the MPM maximum flow algorithm on GPUs $(2010)$

$$ Maximum Flows by Incremental Breadth$-$First Search $(2011)$

$$ A survey of network flow applications $(2013)$

$$ Maximum flow in road networks with speed$-$dependent capacities $$ application to Bangkok

traffic $(2013)$

$$ Efficient Maximum Flow Algorithms $(2014)$

$$ Computing Maximum Flow with Augmenting Electrical Flows $(2016)$

$$ Towards shortest path identification on large networks $(2016)$

For one of the above papers,

$($a$)$ write a report summarizing the paper; and$/$or$,$

$($b$)$ solve an example to illustrate the results in the paper.

Be sure to describe the network flow aspects of the paper in mathematical detail, where

possible.