Shortest Vertex-Disjoint Two-Face Paths in Planar Graphs
Résumé
Let $G$ be a directed planar graph of complexity~$n$, each arc having a nonnegative length. Let $s$ and~$t$ be two distinct faces of $G$; let $s_1,\ldots,s_k$ be vertices incident with~$s$; let $t_1,\ldots,t_k$ be vertices incident with $t$. We give an algorithm to compute $k$ pairwise vertex-disjoint paths connecting the pairs $(s_i,t_i)$ in~$G$, with minimal total length, in $O(kn\log n)$ time.
Origine : Fichiers produits par l'(les) auteur(s)