Dynamically Random Graphs
Alexis Byers, Mallory Reed, Elle VanTilburg · 2013
In this paper, we introduce the idea of a weighted graph that has edges with associated probabilities of being available at discrete time instants. We attempt to solve problems such as the Chinese Postman Problem, finding Eulerian tours, and finding spanning trees in such graphs with the added challenge of minimizing the time spent waiting for edges to become available. We look at a related problem in which we are given a set of n tasks, each with a probability of being available and a completion time, and we provide a strategy for completing k of the n tasks with shortest expected time. Finally, we consider the computation times of our strategies and discuss avenues for further research.