Back to search

National and Kapodistrian University of Athens

Linkages in primal-dual graphs

Abstract

dc:description

Ένα από τα επιτεύγματα με τη μεγαλύτερη επιρροή στη Θεωρία Γραφημάτων υπήρξε χωρίς αμφιβολία η σειρά εργασιών "Ελλάσσονα Γραφήματα" των Neil Robertson και Paul D. Seymour, στην οποία, έπειτα από 23 εργασίες από το 1983 έως το 2011, κατάφεραν να αποδείξουν την εικασία του Wagner. Η εικασία αυτή λέει ότι η κλάση των μη κατευθυνόμενων γραφημάτων, μερικώς διατεταγμένων με τη σχέση ελλάσσονος γραφήματος, αποτελεί well-quasi- διάταξη ή ισοδύναμα, για κάθε κλάση γραφημάτων που είναι κλειστή ως προς ελλάσσονα υπάρχει ένα σύνολο από απαγορευμένα γραφήματα ως ελλάσσονα. Μπορεί να υποστηριχθεί ότι, δεν είναι τόσο το ίδιο το τελικό αποτέλεσμα, όσο ολόκληρη η θεωρία που αναπτύχθηκε στην πορεία που είχε, και συνεχίζει να έχει, τεράστιο αντίκτυπο τόσο στη συνδυαστική όσο και στην αλγοριθμική Θεωρία Γραφημάτων. Μία από τις κυριότερες συνεισφορές τους, η οποία κατέχει και κεντρικό ρόλο στη δουλειά τους, είναι η κατασκευή ενός αλγορίθμου που λύνει το πρόβλημα των ΔΙΑΚΕΚΡΙΜΕΝΩΝ ΜΟΝΟΠΑΤΙΩΝ σε χρόνο f(k)n^3, όπου k είναι το πλήθος των διακεκριμένων μονοπατιών που μας ζητείται να βρούμε. Το βασικό συστατικό της απόδειξής τους είναι η ονομαστή τεχνική της άσχετης κορυφής (για την οποία οι πλήρεις αποδείξεις δόθηκαν σε επόμενο μέρος της σειράς) που χρησιμοποιήθηκε ευρέως στην πορεία. Όσο σπουδαίο κι αν αποδείχθηκε πως είναι το παραπάνω αποτέλεσμα, η συνάρτηση f που εξαρτάται από το k και εμφανίζεται στη χρονική πολυπλοκό- τητα του αλγορίθμου, είναι ασύλληπτα μεγάλη ακόμη και για πολύ μικρές τιμές του k. Για τον λόγο αυτόν, πολλοί ερευνητές θέλησαν να βελτιώσουν αυτήν την παραμετρική εξάρτηση από το k, είτε προσπαθώντας να απλοποιήσουν τις περίπλοκες αποδείξεις των δομικών θεωρημάτων για τη γενική περίπτωση, είτε επικεντρώνοντας την προσοχή τους σε συγκεκριμένες κλάσεις γραφημάτων των οποίων τα δομικά χαρακτηριστικά θα οδηγούσαν, ίσως, σε απλούστερες αποδείξεις και καλύτερη παραμετρική εξάρτηση. Ένα μεγάλο βήμα όσον αφορά την πρώτη κατεύθυνση (παρόλο που το φράγμα για το f(k) είναι 2^(2^(2^(2^Ω(k)))) , το οποίο είναι, σαφώς, ακόμη τεράστιο) έγινε από τους Ken-ichi Kawarabayashi και Paul Wollan στο [20]. Ένα αποφασιστικό βήμα προς τη δεύτερη κατεύθυνση, για την κλάση των επίπεδων γραφημάτων, έγινε από τους Isolde Adler, Stavros G. Kolliopoulos, Philipp Klaus Krause, Daniel Lokshtanov, Saket Saurabh, και Dimitrios M. Thilikos στο [2], όπου αποδεικνύουν ένα φράγμα για το f(k) που είναι απλά εκθετικό ως προς k. Βασιζόμενοι σε αυτήν την τελευταία εργασία, μελετάμε μια επέκταση του προβλήματος των ΔΙΑΚΕΚΡΙΜΕΝΩΝ ΜΟΝΟΠΑΤΙΩΝ στην κλάση των πρωτεύοντων- δυϊκών γραφημάτων και χρησιμοποιώντας την ιδέα άσχετης κορυφής, αποδεικ- νύουμε ένα δομικό θεώρημα το οποίο λέει ότι αν το δεντροπλάτος του πρωτεύοντος- δυϊκού γραφήματος μας είναι αρκούντως μεγάλο, τότε υπάρχει (και μπορεί να εντοπιστεί αλγοριθμικά) ένα τμήμα του το οποίο είναι άσχετο και του οποίου η αφαίρεση από το γράφημα οδηγεί σε ένα απλούστερο και ισοδύναμο στιγμιότυπο του προβλήματος. Επίσης, εξηγούμε πως ένας αλγόριθμος για το πρόβλημα των ΔΙΑΚΕΚΡΙΜΕΝΩΝ ΜΟΝΟΠΑΤΙΩΝ για την κλάση των πρωτεύοντων-δυϊκών γραφημάτων μπορεί να χρησιμοποιηθεί για την κατασκευή αλγορίθμων για προ- βλήματα σε ενεπίπεδα γραφήματα, όπου είναι απαραίτητο να λαμβάνεται υπόψην η τοπολογία της επίπεδης εμβάπτισης που δίνεται ως είσοδος.

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Μανιάτης Σπυρίδων

Rights

Language dc:language
English

Identifiers

dc:identifier.*
Identifier
uoadl:1321199

Chain of custody

source
Harvested from
National and Kapodistrian University of Athens
Base URL
pergamos.lib.uoa.gr/uoa/dl/frontend/oaipmh
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Μανιάτης Σπυρίδων. Linkages in primal-dual graphs. 2016. https://pergamos.lib.uoa.gr/uoa/dl/object/1321199