This thesis studies network flow problems. More specifically, we mostly consider single-sink multicommodity flows with constraints on how nodes may "process" flow. In the unsplittable flow problem, the demand sent from a source to its destination must follow a single path. In d-furcated flows, each node is allowed to send flow to at most d out-neighbours. The special case with d equal to 1 is called confluent flow. We make a survey of many of the known algorithms to tackle these problems. Finally, we present a new result which uses confluent flows and a special type of clustering we call rooted clustering to give an approximation algorithm for the maximum edge-disjoint path problem. This algorithm routes a constant fraction of the demand with maximum edge congestion at most 3, thus improving the previous known bound of 4. / Cette thèse étudie les problèmes de flots sur réseau. Plus particulièrement, nous portons notre attention sur les flots à puits unique et à multiples sources avec des contraintes de degré. Dans le problème de flot indivisible, la demande envoyée par une source doit suivre un chemin unique. Dans le problème de flot d-furqué, chaque sommet peut envoyer du flot à d voisins au plus. Le cas particulier avec d égal à 1 est appelé flot confluent. Nous présentons un survol de certains des algorithmes utilisés pour attaquer ces problèmes. Finalement, nous présentons un nouveau résultat qui utilise les flots confluents et un type particulier de regroupement des sommets que nous appelons regroupement enraciné pour obtenir un algorithme d'approximation pour le problème de maximisation des chemins disjoints (en terme d'arêtes). Cet algorithme satisfait une fraction constante de la demande totale avec une congestion d'arête d'au plus 3. Il s'agit donc d'une amélioration de la meilleure borne précédente de 4.
| Identifer | oai:union.ndltd.org:LACETR/oai:collectionscanada.gc.ca:QMM.66815 |
| Date | January 2009 |
| Creators | Séguin-Charbonneau, Loïc |
| Contributors | Frederick Shepherd (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.0635 seconds