Disjoint paths

Kriesell's Conjecture ★★

Author(s): Kriesell

\begin{conjecture} Let $G$ be a graph and let $T\subseteq V(G)$ such that for any pair $u,v\in T$ there are $2k$ edge-disjoint paths from $u$ to $v$ in $G$. Then $G$ contains $k$ edge-disjoint trees, each of which contains $T$. \end{conjecture}

Keywords: Disjoint paths; edge-connectivity; spanning trees

Approximation Ratio for Maximum Edge Disjoint Paths problem ★★

Author(s): Bentz

\begin{conjecture} Can the approximation ratio $O(\sqrt{n})$ be improved for the Maximum Edge Disjoint Paths problem (MaxEDP) in planar graphs or can an inapproximability result stronger than $\mathcal{APX}$-hardness? \end{conjecture}

Keywords: approximation algorithms; Disjoint paths; planar graph; polynomial algorithm

Syndicate content