Unit:
Κατεύθυνση Αλγόριθμοι, Λογική και Διακριτά Μαθηματικά (Α.Λ.ΜΑ.)Πληροφορική
Author:
Stamoulis Giannos
Supervisors info:
Σταύρος Κολλιόπουλος, Καθηγητής, Τμήμα Πληροφορικής και Τηλεπικοινωνιών, Εθνικό και Καποδιστριακό Πανεπιστήμιο Αθηνών
Original Title:
Decompositions and Algorithms for the Disjoint Paths Problem in Planar Graphs
Translated title:
Decompositions and Algorithms for the Disjoint Paths Problem in Planar Graphs
Summary:
> In the Disjoint Paths Problem, given a graph G and a set of k pairs of terminals, we ask whether the pairs of terminals can be linked by pairwise disjoint paths.
> In the Graph Minors series of 23 papers between 1984 and 2011, Neil Robertson and Paul D. Seymour, among other great results that heavily influenced Graph Theory, provided an f(k)\cdot n^{3} algorithm for the Disjoint Paths Problem. To achieve this, they introduced the irrelevant vertex technique according to which in every instance of treewidth greater than g(k) there is an “irrelevant” vertex whose removal creates an equivalent instance of the problem.
>
> We study the problem in planar graphs and we prove that for every fixed k every instance of the Planar Disjoint Paths Problem can be transformed to an equivalent one that has bounded treewidth, by simultaneously discarding a set of vertices of the given planar graph. As a consequence the Planar Disjoint Paths Problem can be solved in linear time for every fixed number of terminals.
Main subject category:
Science
Keywords:
parametrized algorithms, parametrized complexity, disjoint paths problem, linkages, irrelevant vertex technique, treewidth
