δείτε την πρωτότυπη σελίδα τεκμηρίου στον ιστότοπο του αποθετηρίου του φορέα για περισσότερες πληροφορίες και για να δείτε όλα τα ψηφιακά αρχεία του τεκμηρίου*
Decompositions and Algorithms for the Disjoint Paths Problem in Planar Graphs
Στο πρόβλημα των Διακεκριμενων Μονοπατιων μας ζητείται να εξετάσουμε, δεδομένου ενός γραφήματος G και ενος συνόλου k ζευγών τερματικών,αν τα ζεύγη των τερματικών μπορούν να συνδεθούν με διακεκριμένα μονοπάτια. Στα "Graph Minors", μια σειρά 23 εργασιών μεταξύ 1984 και 2011, οι Neil Robertson και Paul D. Seymour, ανάμεσα σε άλλα σπουδαία αποτελέσματα που επηρέασαν βαθιά την Θεωρία Γραφημάτων, παρουσίασαν έναν f(k)*n^3 αλγόριθμο για το πρόβλημα των Διακεκριμενων Μονοπατιων. Για να το καταφέρουν αυτό, εισήγαγαν την "τεχνκή της άσχετης κορυφής" σύμφωνα με την οποία σε κάθε στιγμιότυπο δεντροπλάτους μεγαλύτερου του g(k) υπάρχει μια "άσχετη" κορυφή της οποίας η αφαίρεση δημιουργεί ένα ισοδύναμο στιγμιότυπο του προβλήματος.
Εδώ μελετάμε το πρόβλημα σε επίπεδα γραφήματα και αποδεικνύουμε ότι για κάθε σταθερό k κάθε στιγμιότυπο του προβλήματος των Διακεκριμενων Μονοπατιων σε επιπεδα γραφηματα μπορεί να μετασχηματιστεί σε ένα ισοδύναμο που έχει φραγμένο δενδροπλάτος, αφαιρώντας ταυτόχρονα ένα σύνολο κορυφών από το δεδομένο επίπεδο γράφημα. Ως συνέπεια αυτού, το πρόβλημα των Διακεκριμένων Μονοπατιών σε επίπεδα γραφήματα μπορεί να λυθεί σε γραμμικό χρόνο για κάθε σταθερό πλήθος τερματικών.
(EL)
> 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.
(EN)
*Η εύρυθμη και αδιάλειπτη λειτουργία των διαδικτυακών διευθύνσεων των συλλογών (ψηφιακό αρχείο, καρτέλα τεκμηρίου στο αποθετήριο) είναι αποκλειστική ευθύνη των αντίστοιχων Φορέων περιεχομένου.
Βοηθείστε μας να κάνουμε καλύτερο το OpenArchives.gr.
Εθνικό και Καποδιστριακό Πανεπιστήμιο Αθηνών
