Shortest Vertex-Disjoint Two-Face Paths in Planar Graphs
| dc.creator | De Verdière, Eric Colin | |
| dc.creator | Schrijver, Alexander | |
| dc.date | 2008-02-20 | |
| dc.date.accessioned | 2026-07-07T09:22:02Z | |
| dc.date.available | 2026-07-07T09:22:02Z | |
| dc.description | 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,...,s_k$ be vertices incident with $s$; let $t_1,...,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. | |
| dc.identifier | https://arxiv.org/abs/0802.2845 | |
| dc.identifier | http://arxiv.org/abs/0802.2845 | |
| dc.identifier | Dans Proceedings of the 25th Annual Symposium on the Theoretical Aspects of Computer Science - STACS 2008, Bordeaux : France (2008) | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/155234 | |
| dc.subject | Data Structures and Algorithms | |
| dc.subject | Combinatorics | |
| dc.title | Shortest Vertex-Disjoint Two-Face Paths in Planar Graphs | |
| dc.type | text |