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