Min-Sum 2-Paths Problems

Title

Min-Sum 2-Paths Problems

 

Abstract

An orientation of an undirected graph $G$ is a directed graph obtained by replacing each edge $\{u,v\}$ of $G$ by exactly one of the arcs $(u,v)$ or $(v,u)$.

 

In the min-sum $2$-paths orientation problem, the input is an undirected graph $G$ and two ordered pairs $(s_1,t_1)$, $(s_2,t_2)$. The goal is to find an orientation of $G$ that minimizes the sum of the distances from $s_1$ to $t_1$ and $s_2$ to $t_2$.

 

In this talk we present a PTAS for this problem and show a connection with the more famous min-sum $2$ edge disjoint paths problem, where we are searching for two edge disjoint paths of minimum total length.

 

About the presenter

Alex Popa completed his PhD at the University of Bristol in 2011. Then, he was a post-doc at Aalto University for two years and currently he is an Assistant Professor at Masaryk University in Brno, Czech Republic. His research interests are: algorithms for NP-hard problems, string algorithms and bioinformatics.

 

You can find more information on his web-page: http://fi.muni.cz/~popa.