Back to search

National and Kapodistrian University of Athens

On the computability of obstruction sets for well-quasi-ordered graph classes

Abstract

dc:description

Στην παρούσα διπλωματική εργασία θα μελετήσουμε αλγόριθμους για τον υπολογισμό συνόλων παρεμπόδησης καλώς μερικώς διατεταγμένων κλάσεων γραφημάτων. Το Θεώρημα Ελασσόνων Γραφημάτων (ΘΕΓ), των Neil Robertson και Paul Seymour (Graph Minor Theorem) εγγυάται πως κάθε κλάση κλειστή ως προς τη σχέση των ελασσόνων έχει πεπερασμένο σύνολο παρεμόδησης. Αν η C είναι μια τέτοια κλάση, τότε το σύνολο παρεμπόδησης της C είναι το ελαχιστικό σύνολο γραφημάτων H έτσι ώστε, ένα γράφημα G ανήκει στην κλάση C αν και μόνο αν κανένα από τα γραφήματα στο σύνολο H δεν περιέχεται ως ελάσσον στο G. Το αντίστοιχο αποτέλεσμα για μια άλλη καλή μερική διάταξη, την σχέση της εμβύθισης, αποδείχθηκε στην ίδια σειρά εργασιών (Graph Minors). Όμως αυτά τα αποτελέσματα είναι μη-κατασκευαστικά: ξέρουμε πως κάθε κλάση κλειστή ως προς ελάσσονα ή εμβυθίσεις έχει πεπερασμένο σύνολο παρεμπόδησης αλλά από αυτά τα αποτελέσματα δεν υποδεικνύουν κάποιο αλγόριθμο για να το υπολογίσουμε. Οι K. Cattell, M. J. Dinneen, R. Downey, M. R. Fellows and M. Langston στην εργασία "On computing graph minor obstruction sets" και οι I. Adler, M. Grohe and S. Kreutzer στην εργασία "Computing Excluded Minors" παρουσιάζουν αλγόριθμους για να ξεπεράσουμε αυτό το πρόβλημα στις κλάσεις γραφημάτων κλειστές ως προς ελάσσονα, καθώς και εφαρμογές των μεθόδων τους, όπως το πρόβλημα της ένωσης. Προσαρμόζοντας τις μεθόδους της δεύτερης από τις προηγουμένες εργασίες σε εμβυθήσεις οι Α. Γιαννοπούλου, Δ. Ζώρος και ο συγγραφέας, ύπο την επίβλεψη του Δ. Μ. Θηλυκού αποδεικνύουν το αντίστοιχο αποτέλεσμα για κλάσεις γραφημάτων κλειστές ως προς εμβύθιση, καθώς και έναν αλγόριθμο για το πρόβλημα της ένωσης για εμβυθίσεις.

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Σαλέμ Ιωσήφ

Rights

Language dc:language
English

Identifiers

dc:identifier.*
Identifier
uoadl:1321308

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

Σαλέμ Ιωσήφ. On the computability of obstruction sets for well-quasi-ordered graph classes. 2012. https://pergamos.lib.uoa.gr/uoa/dl/object/1321308