Back to search

National and Kapodistrian University of Athens

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

Abstract

dc:description

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.

Degree

thesis:*
Grantor dc:publisher
National and Kapodistrian University of Athens
Year dc:date
2014

Author and committee

dc:creator, dc:contributor.*
Authors dc:creator
  • Koutsonas, Athanasios
  • Κουτσώνας, Αθανάσιος

Subjects

dc:subject × 12

Rights

Language dc:language
gre

Identifiers

dc:identifier.*
Identifier
10.12681/eadd/35055

Chain of custody

source
Harvested from
Greek National Archive of PhD Theses
Base URL
phdtheses.ekt.gr/eadd_oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Koutsonas, Athanasios; Κουτσώνας, Αθανάσιος. Διδιαστατότητα: θεωρία και αλγοριθμικές εφαρμογές. National and Kapodistrian University of Athens, 2014. http://hdl.handle.net/10442/hedi/35055