Πολλά συνδυαστικά υπολογιστικά προβλήματα είναι στη γενική μορφή τους δύσβατα,
υπό την έννοια πως ακόμη και για εισόδους μέτριου μεγέθους, η εύρεση μιας
ακριβούς και βέλτιστης λύσης είναι μάλλον ανέφικτη, δεδομένου ότι συνήθως
απαιτεί την κλήση αλγορίθμων, των οποίων η χρονική πολυπλοκότητα είναι εκθετική
ως προς το μέγεθος του προβλήματος. Συχνά τα προβλήματα αυτά μπορούν να
οριστούν σε γραφήματα. Πρόσθετες δομικές ιδιότητες ενός γραφήματος, όπως η
εμβαπτισιμότητα σε κάποια επιφάνεια, παρέχουν μια λαβή για το σχεδιασμό
αποδοτικότερων αλγορίθμων. Η θεωρία της διδιαστατότητας αναπτύχθηκα στα πλαίσια
της Παραμετρικής Πολυπλοκότητας και, βασιζόμενη στα αποτελέσματα της θεωρίας
των Ελασσόνων Γραφημάτων, παρέχει ένας μετα-αλγοριθμικό πλαίσιο για την
αντιμετώπιση ενός συνόλου προβλημάτων σε πλατύ φάσμα κλάσεων γραφημάτων, πιο
συγκεκριμένα σε όλες τις γενικεύσεις γραφημάτων εμβαπτίσιμων σε κάποια
επιφάνεια. Στη διδακτορική διατριβή αυτή θεωρούμε ζητήματα συνδυαστικής φύσης
σχετικά με την εφαρμογή της θεωρίας της Διδιαστατότητας και τις δυνατότητες
επέκτασης του πεδίου εφαρμογής της.
(EL)
Many combinatorial computational problems are considered in their general
form intractable, in the sense that even for modest size problems, providing
an exact optimal solution is practically infeasible, as it typically involves
the
use of algorithms whose running time is exponential in the size of the problem.
Often these problems can be modeled by graphs. Then, additional structural
properties of a graph, such as surface embeddability, can provide a handle for
the design of more ecient algorithms. The theory of Bidimensionality, dened
in the context of Parameterized Complexity, builds on the celebrated results of
Graph Minor theory and establishes
a meta algorithmic framework for addressing problems in a broad range of graph
classes, namely all generalizations of graphs embeddable on some surface. In
this doctoral thesis we explore topics of combinatorial nature related to the
implementation of the theory of Bidimensionality and to the possibilities of
the extension of its applicability range.
(EN)
/aggregator-openarchives/portal/institutions/uoa
