Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Lovász, Vectors, Graphs and Codes Read chapter Read first chapter

2019 | OriginalPaper | Chapter

Finding k Partially Disjoint Paths in a Directed Planar Graph

Author : Alexander Schrijver

Published in: Building Bridges II

Publisher: Springer Berlin Heidelberg

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

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.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter Subspace Arrangements, Graph Rigidity and Derandomization Through Submodular Optimization
next chapter Embedding Graphs into Larger Graphs: Results, Methods, and Problems
Footnotes
1
If a and b are periods of \(x=(x_1,\ldots ,x_n)\) with \(a<b\) and \(a+b\le n\), then \(b-a\) is a period of x. For let \(1\le i\le n-(b-a)\). We show \(x_{i+(b-a)}=x_i\). If \(i\le n-b\) then \(x_{i+(b-a)}=x_{(i+b)-a}=x_{i+b}=x_i\). If \(i>n-b\) then \(i>a\) (as \(i>n-b\ge a\), since \(a+b\le n\) by assumption), hence \(x_{i+(b-a)}=x_{(i-a)+b}=x_{i-a}=x_i\).
 
2
Let A a polynomial-time algorithm that finds a solution for feasible instances. When we apply A to any instance, then if feasible, we find a feasible solution, and if infeasible, A gets stuck or has not delivered a solution in polynomial time.
 
Literature
1.
A.V. Anisimov, D.E. Knuth, Inhomogeneous sorting, International Journal of Computer and Information Sciences 8 (1979) 255–260.MathSciNetCrossRef
2.
A. Baudisch, Kommutationsgleichungen in semifreien Gruppen, Acta Mathematica Academiae Scientiarum Hungaricae 29 (1977) 235–249.MathSciNetCrossRef
3.
M. Cygan, D. Marx, M. Pilipczuk, M. Pilipczuk, The planar directed \(k\)-vertex-disjoint paths problem is fixed-parameter tractable, in: 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, IEEE, 2013, pp. 197–206.
4.
V. Diekert, On the Knuth-Bendix completion for concurrent processes, Theoretical Computer Science 66 (1989) 117–136.MathSciNetCrossRef
5.
V. Diekert, Combinatorics on Traces, Lecture Notes in Computer Science 454, Springer, Berlin, 1990.
6.
7.
E.S. Esyp, I.V. Kazachkov, V.N. Remeslennikov, Divisibility theory and complexity of algorithms for free partially commutative groups, in: Groups, Languages, Algorithms, Contemporary Mathematics 378, American Mathematical Society, Providence, R.I., 2005, pp. 319–348.
8.
S. Fortune, J. Hopcroft, J. Wyllie, The directed subgraph homeomorphism problem, Theoretical Computer Science 10 (1980) 111–121.MathSciNetCrossRef
9.
K. Kawarabayashi, Y. Kobayashi, B. Reed, The disjoint paths problem in quadratic time, Journal of Combinatorial Theory, Series B 102 (2012) 424–435.MathSciNetCrossRef
10.
J.F. Lynch, The equivalence of theorem proving and the interconnection problem, (ACM) SIGDA Newsletter 5:3 (1975) 31–36.
11.
R.C. Lyndon, P.E. Schupp, Combinatorial Group Theory, Springer, Berlin, 1977.MATH
12.
W. Magnus, A. Karrass, D. Solitar, Combinatorial Group Theory, Wiley-Interscience, New York, 1966.MATH
13.
B.A. Reed, N. Robertson, A. Schrijver, P.D. Seymour, Finding disjoint trees in planar graphs in linear time, in: Graph Structure Theory (N. Robertson, P. Seymour, eds.), Contemporary Mathematics 147, American Mathematical Society, Providence, R.I., 1993, pp. 295–301.
14.
N. Robertson, P.D. Seymour, Graph minors. XIII. The disjoint paths problem, Journal of Combinatorial Theory, Series B 63 (1995) 65–110.
15.
A. Schrijver, Finding \(k\) disjoint paths in a directed planar graph, SIAM Journal on Computing 23 (1994) 780–788.MathSciNetCrossRef
16.
A. Schrijver, Combinatorial Optimization – Polyhedra and Efficiency, Springer, Berlin, 2003.MATH
17.
18.
C. Wrathall, The word problem for free partially commutative groups, Journal of Symbolic Computation 6 (1988) 99–104.MathSciNetCrossRef
Metadata
Title
Finding k Partially Disjoint Paths in a Directed Planar Graph
Author
Alexander Schrijver
Copyright Year
2019
Publisher
Springer Berlin Heidelberg
Book
Building Bridges II

Print ISBN: 978-3-662-59203-8

Electronic ISBN: 978-3-662-59204-5

Copyright Year: 2019

DOI
https://doi.org/10.1007/978-3-662-59204-5_13

Premium Partner

    Image Credits