Finding k Partially Disjoint Paths in a Directed Planar Graph
| Autor: | Alexander Schrijver |
|---|---|
| Rok vydání: | 2019 |
| Předmět: |
Discrete mathematics
Mathematics::Combinatorics Mathematics::Commutative Algebra 010102 general mathematics 0102 computer and information sciences Disjoint sets Directed graph Computer Science::Computational Geometry Surface (topology) 01 natural sciences Planar graph Combinatorics symbols.namesake Computer Science::Discrete Mathematics 010201 computation theory & mathematics Path (graph theory) symbols 0101 mathematics Computer Science::Data Structures and Algorithms Mathematics |
| Zdroj: | Bolyai Society Mathematical Studies ISBN: 9783662592038 |
| DOI: | 10.1007/978-3-662-59204-5_13 |
| Popis: | The partially disjoint paths problem is: given: a directed graph, vertices \(r_1,s_1,\ldots ,r_k,s_k\), and a set F of pairs \(\{i,j\}\) from \(\{1,\ldots ,k\}\), find: for each \(i=1,\ldots ,k\) a directed \(r_i-s_i\) path \(P_i\) such that if \(\{i,j\}\in F\) then \(P_i\) and \(P_j\) are disjoint. We show that for fixed k, this problem is solvable in polynomial time if the directed graph is planar. More generally, the problem is solvable in polynomial time for directed graphs embedded on a fixed compact surface. Moreover, one may specify for each edge a subset of \(\{1,\ldots ,k\}\) prescribing which of the \(r_i-s_i\) paths are allowed to traverse this edge. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|