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

Περίληψη σε άλλη γλώσσα

Many combinatorial computational problems are considered in their generalform intractable, in the sense that even for modest size problems, providingan exact optimal solution is practically infeasible, as it typically involves theuse of algorithms whose running time is exponential in the size of the problem.Often these problems can be modeled by graphs. Then, additional structuralproperties of a graph, such as surface embeddability, can provide a handle forthe design of more ecient algorithms.The theory of Bidimensionality, dened in the context of ParameterizedComplexity, builds on the celebrated results of Graph Minor theory and establishesa meta algorithmic framework for addressing problems in a broadrange of graph classes, namely all generalizations of graphs embeddable onsome surface.In this doctoral thesis we explore topics of combinatorial nature related tothe implementation of the theory of Bidimensionality and to the possibilitiesof the extension of its applicability range.
Πρέπει να είστε εγγεγραμένος χρήστης για έχετε πρόσβαση σε όλες τις υπηρεσίες του ΕΑΔΔ  Είσοδος /Εγγραφή

Όλα τα τεκμήρια στο ΕΑΔΔ προστατεύονται από πνευματικά δικαιώματα.

Διεύθυνση Handle
http://hdl.handle.net/10442/hedi/35055
ND
35055
Εναλλακτικός τίτλος
Bidimensionality: theory and algorithmic applications
Συγγραφέας
Κουτσώνας, Αθανάσιος Λάμπρος
Ημερομηνία
2014
Ίδρυμα
Εθνικό και Καποδιστριακό Πανεπιστήμιο Αθηνών (ΕΚΠΑ). Σχολή Θετικών Επιστημών. Τμήμα Μαθηματικών
Εξεταστική επιτροπή
Θηλυκός Δημήτριος
Ζάχος Ευστάθιος
Κολλιόπουλος Σταύρος
Κυρούσης Ελευθέριος
Ράπτης Ευάγγελος
Παγουρτζής Αριστείδης
Δρακόπουλος Μιχαήλ
Επιστημονικό πεδίο
Φυσικές Επιστήμες
Μαθηματικά
Επιστήμες Ηλεκτρονικών Υπολογιστών & Πληροφορικής
Λέξεις-κλειδιά
Διδιαστατότητα; Αλγόριθμοι; Θεωρία γραφημάτων
Χώρα
Ελλάδα
Γλώσσα
Ελληνικά
Άλλα στοιχεία
170 σ., σχημ., ευρ.