Shortest vertex-disjoint two-face paths in planar graphs
| Authors |
|
|---|---|
| Publication date | 2011 |
| Journal | ACM Transactions on Algorithms (TALG) |
| Volume | Issue number | 7 | 2 |
| Number of pages | 12 |
| Organisations |
|
| 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 s1,…,sk be vertices incident with s let t1,…,tk be vertices incident with t. We give an algorithm to compute k pairwise vertex-disjoint paths connecting the pairs (si,ti) in G, with minimal total length, in O(knlog n) time. |
| Document type | Article |
| Language | English |
| Published at | https://doi.org/10.1145/1921659.1921665 |
| Permalink to this page | |