A class of graphs is minor closed if it contains all the minors of its elements. In this thesis, we discuss optimization algorithms for the graphs in certain minor-closed classes that exploit their structural properties. The algorithms use special tree- decompositions of these graphs as well as some other structural theorems. We present new results on finding odd cycle covers of bounded size. We present a new algorithm to do so in arbitrary graphs, and show that a variant of this algorithm runs in linear time on the class of graphs obtained by excluding any fixed graph H as a minor. / Une classe de graphes est dite close par mineur si elle contient tous les mineurs de ses éléments. Dans cette thèse, nous discutons des algorithmes d'optimisation pour certaines classes closes par mineur qui exploitent leur structure. Ces algorithmes sont basés sur des décompositions arborescentes spéciales de ces graphes et quelques autres théorèmes structurels. Nous présentons de nouveaux résultats sur la recherche de couvertures de cycles impairs de taille limitée. Nous présentons un nouvel algorithme pour résoudre ce problème dans un graphe arbitraire, et montrons qu'une variante de cet algorithme prend un temps linéaire sur la classe de graphes obtenus en excluant n'importe quel graphe fixe H comme mineur.
| Identifer | oai:union.ndltd.org:LACETR/oai:collectionscanada.gc.ca:QMM.32515 |
| Date | January 2009 |
| Creators | Kapadia, Rohan |
| Contributors | Bruce Alan Reed (Internal/Supervisor) |
| Publisher | McGill University |
| Source Sets | Library and Archives Canada ETDs Repository / Centre d'archives des thèses électroniques de Bibliothèque et Archives Canada |
| Language | English |
| Detected Language | French |
| Type | Electronic Thesis or Dissertation |
| Format | application/pdf |
| Coverage | Master of Science (Department of Mathematics and Statistics) |
| Rights | All items in eScholarship@McGill are protected by copyright with all rights reserved unless otherwise indicated. |
| Relation | Electronically-submitted theses. |
Page generated in 0.002 seconds