Partial Orderings and Algorithms on Graphs

Doctoral Dissertation uoadl:1309689 549 Read counter

Unit:
Τομέας Μαθηματικής Ανάλυσης
Library of the School of Science
Deposit date:
2013-04-15
Year:
2013
Author:
Γιαννοπούλου Αρχοντία
Dissertation committee:
Δημήτριος Μ. Θηλυκός Αναπληρωτής Καθηγητής
Original Title:
Partial Orderings and Algorithms on Graphs
Languages:
English
Translated title:
Μερικές Διατάξεις και Αλγόριθμοι σε Γραφήματα
Summary:
In the Graph Minors project, N. Robertson and P. Seymour, proved a series of
structural and 
algorithmic results. Some of them, such as the Strong and the Weak Structure
Theorem, the Excluded 
Grid Theorem and the algorithm for Minor Containment, constitute a rich source
of many more structural  as well as algorithmic results.
Furthermore, the development of Graph Minor Theory coincided with and
influenced the development 
of a new branch of Complexity, namely the Parameterized Complexity Theory,
introduced by R. Downey  and M. Fellows. In this doctoral thesis we deal with a
series of issues in Graph Minor Theory and Parameterized  Complexity as well as
the dependence of these two areas. 
Keywords:
Graph Minor Theory , Graph Searching , Excluded Grid Theorem, Bidimenstionality Theory, Treewidth
Index:
Yes
Number of index pages:
XV-XVII, XIX, 297-304
Contains images:
Yes
Number of references:
222
Number of pages:
XX, 304
document.pdf (1 MB) Open in new window