mpla.math.uoa.gr
Font size: Αα Αα Αα hide gadgets
You are here: Theses » MSc » Iosif Salem Anonymously browsing from 54.224.187.45 at 09:28:47, 23-11-2017. login

MSc thesis of Iosif Salem

On the computability of obstruction sets for well-quasi-ordered graph classes

Supervisor: Dimitrios M. Thilikos

In this MSc thesis we are going to present algorithms for computing obstruction sets of well–quasi–ordered graph classes. Neil Robertson and Paul Seymour’s Graph Minor Theorem (GMT) [27] guarantees that any minor–closed graph class has a finite obstruc- tion set. If C is such a class, the obstruction set of C, obsm(C), is the minimal set of graphs H such that G belongs to C if and only if none of the graphs in H is contained as a minor in G. The analogous result for another well–quasi–ordering, the immersion ordering, was shown in the same series of papers (Graph Minors), in [30]. But this results are non-constructive; we know that a minor or immersion–closed graph class has a finite obstruction set but the GMT does not imply any algorithm for computing it. K. Cattell, M. J. Dinneen, R. Downey, M. R. Fellows and M. Langston in “On computing graph minor obstruction sets” [6] and I. Adler, M. Grohe and S. Kreutzer in “Computing Excluded Minors” [1] present algorithms to overcome this problem for minor–closed graph classes, as well as, applications of their methods proving that the obstruction sets of various graph classes are computable, such as the union problem. By adapting some of the methods of [1] to immersions, the analogue result for immersion obstruction sets and an algorithm for the union problem on immersion–closed graph classes are proven in [17] by A. Giannopoulou, D. Zoros and the author, under the supervision of D. M. Thilikos.

Defended: Sept. 17, 2012.

Download

Download thesis.

Reporter

Page updates

No recent updates.

Feeds RSS and Atom feeds

posts
all posts RSS
news RSS
announcements RSS
website news RSS
events
all events RSS
defenses RSS
exams RSS
seminars RSS
graduations RSS
Web standards: XHTML1.0, CSS3.
© 1996 – 2017 MPLA: Graduate program in Logic, Algorithms and Computation.
Contact the webmaster.