Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.
Publication
Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.
We present an O(p*n) algorithm for the problem of finding disjoint simple paths of minimum total length between p given pairs of terminals on oriented partial 2-trees with n nodes and positive or negative arc lengths. The algorithm is in O(n) if all terminals are distinct nodes. We characterize the convex hull of the feasible solution set for the case p = 2.