LIPIcs.STACS.2008.1347.pdf
- Filesize: 194 kB
- 12 pages
Document
Shortest Vertex-Disjoint Two-Face Paths in Planar Graphs
Authors
-
Part of:
Volume:
25th International Symposium on Theoretical Aspects of Computer Science (STACS 2008)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Symposium on Theoretical Aspects of Computer Science (STACS) - License:
Creative Commons Attribution-NoDerivs 3.0 Unported license
- Publication Date: 2008-02-06
Cite AsGet BibTex
Éric Colin de Verdiére and Alexander Schrijver. Shortest Vertex-Disjoint Two-Face Paths in Planar Graphs. In 25th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 1, pp. 181-192, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)
https://doi.org/10.4230/LIPIcs.STACS.2008.1347
https://doi.org/10.4230/LIPIcs.STACS.2008.1347
Abstract
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(knlog n)$ time.
Keywords
- Algorithm
- planar graph
- disjoint paths
- shortest path
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads