Διδιαστατότητα: Θεωρία και Αλγοριθμικές Εφαρμογές

Διδακτορική Διατριβή uoadl:1308818 617 Αναγνώσεις

Μονάδα:
Τομέας Μαθηματικής Ανάλυσης
Βιβλιοθήκη Σχολής Θετικών Επιστημών
Ημερομηνία κατάθεσης:
2014-03-12
Έτος εκπόνησης:
2014
Συγγραφέας:
Κουτσώνας Αθανάσιος
Στοιχεία επταμελούς επιτροπής:
Αναπλ. Καθηγητής Δημήτριος Μ. Θηλυκός (επιβλέπων)
Πρωτότυπος Τίτλος:
Διδιαστατότητα: Θεωρία και Αλγοριθμικές Εφαρμογές
Γλώσσες διατριβής:
Ελληνικά
Μεταφρασμένος τίτλος:
Bidimensionality: Theory and Algorithmic Applications
Περίληψη:
Πολλά συνδυαστικά υπολογιστικά προβλήματα είναι στη γενική μορφή τους δύσβατα,
υπό την έννοια πως ακόμη και για εισόδους μέτριου μεγέθους, η εύρεση μιας
ακριβούς και βέλτιστης λύσης είναι μάλλον ανέφικτη, δεδομένου ότι συνήθως
απαιτεί την κλήση αλγορίθμων, των οποίων η χρονική πολυπλοκότητα είναι εκθετική
ως προς το μέγεθος του προβλήματος. Συχνά τα προβλήματα αυτά μπορούν να
οριστούν σε γραφήματα. Πρόσθετες δομικές ιδιότητες ενός γραφήματος, όπως η
εμβαπτισιμότητα σε κάποια επιφάνεια, παρέχουν μια λαβή για το σχεδιασμό
αποδοτικότερων αλγορίθμων. Η θεωρία της διδιαστατότητας αναπτύχθηκα στα πλαίσια
της Παραμετρικής Πολυπλοκότητας και, βασιζόμενη στα αποτελέσματα της θεωρίας
των Ελασσόνων Γραφημάτων, παρέχει ένας μετα-αλγοριθμικό πλαίσιο για την
αντιμετώπιση ενός συνόλου προβλημάτων σε πλατύ φάσμα κλάσεων γραφημάτων, πιο
συγκεκριμένα σε όλες τις γενικεύσεις γραφημάτων εμβαπτίσιμων σε κάποια
επιφάνεια. Στη διδακτορική διατριβή αυτή θεωρούμε ζητήματα συνδυαστικής φύσης
σχετικά με την εφαρμογή της θεωρίας της Διδιαστατότητας και τις δυνατότητες
επέκτασης του πεδίου εφαρμογής της.
Λέξεις-κλειδιά:
Διδιαστατότητα, Αλγόριθμοι, Θεωρία Γραφημάτων, Θεωρία Μητροειδών, Ελάσσονα
Ευρετήριο:
Όχι
Αρ. σελίδων ευρετηρίου:
0
Εικονογραφημένη:
Ναι
Αρ. βιβλιογραφικών αναφορών:
151
Αριθμός σελίδων:
170