Generalized Minimum Eccentricity Shortest Path Problem in Tree-Structured Graphs

The primary objective of our research is to explore a problem in theoretical computer science related to finding particular paths within networks. Specifically, we are interested in finding a set of paths within very large networks such that the distance between any point within the network and one of these paths is as small as possible. This is a generalization of a previously researched problem called the Minimum Eccentricity Shortest Path (MESP) Problem. In this presentation, we give a formal introduction to the generalized version of this problem and its hardness. Additionally, we give an overview of how different classes of networks can have more efficient solutions when we take advantage of particular properties. Using this, we give an efficient +1-approximation algorithm to the generalized MESP Problem for a particular class of networks and describe how our approach could be generalized to work for a broader class of networks. Finally, we discuss the applications of this problem to biology and other areas of computer science