Résolution exacte et approchée de problèmes de multiflot entier et de multicoupe : algorithmes et complexité / Cédric Bentz ; sous la direction de Marie-Christine Costa

Date :

Editeur / Publisher : [S.l.] : [s.n.] , 2006

Type : Livre / Book

Type : Thèse / Thesis

Langue / Language : français / French

Flots (théorie des graphes)

Coupes (théorie des graphes)

Optimisation combinatoire

Problèmes extrémaux (mathématiques)

Arbres (théorie des graphes)

Approximation polynomiale

Classification Dewey : 519.6

Costa, Marie-Christine (1952-....) (Directeur de thèse / thesis advisor)

Conservatoire national des arts et métiers (France ; 1794-....) (Organisme de soutenance / degree-grantor)

Relation : Résolution exacte et approchée de problèmes de multiflot entier et de multicoupe : algorithmes et complexité / Cédric Bentz ; sous la direction de Marie-Christine Costa / Lille : Atelier national de reproduction des thèses , 2006

Résumé / Abstract : Dans cette thèse, on s'intéresse à des problèmes de multiflot entier et de multicoupe, qui généralisent les problèmes classiques de flot maximum et de coupe minimum. Deux aspects de ces problèmes y sont étudiés en particulier : la résolution exacte en temps polynomial et l'approximation polynomiale. Du point de vue de la résolution exacte, nos principales contributions portent sur les sujets suivants : chemins disjoints dans les graphes de nombre cyclomatique borné ; multicoupes dans les graphes orientés sans circuits, dans les graphes non orientés de largeur d'arbre bornée et dans les graphes planaires ; multiflots entiers dans les anneaux ; multicoupes et multiflots entiers dans certains cas particuliers de grilles. Du point de vue de l'approximation polynomiale, nos principales contributions portent sur les sujets suivants : chemins disjoints dans les graphes planaires à k niveaux d'arêtes ; multiflots entiers dans les graphes de nombre cyclomatique borné ; multicoupes dans les graphes orientés non pondérés de largeur d'arbre et de degré maximum bornés ; flots multiterminaux entiers dans les graphes orientés. Nous décrivons également une nouvelle heuristique pour trouver un multiflot entier maximum dans un graphe non orienté, et la testons sur des instances générées aléatoirement.

Résumé / Abstract : In this thesis, we consider integral multiflow and multicut problems, which generalize the classical max flow and min cut problems. Two aspects of these problems are studied in particular : polynomial-time resolution and polynomial approximation. Concerning the first aspect, our main contributions focus on the following points : disjoint paths in graphs of bounded cyclomatic number ; multicuts in directed acyclic graphs, in undirected graphs of bounded tree-width and in planar graphs ; integral multiflows in rings ; multicuts and integral multiflows in several special types of grids. Concerning the second aspect, our main contributions focus on the following points : disjoint paths in k-edge-outerplanar graphs ; integral multiflows in graphs of bounded cyclomatic number ; multicuts in unweighted digraphs of bounded maximum degree and bounded tree-width ; integral multiterminal flows in digraphs. We also describe a new heuristic to find a maximum integral multiflow in an undirected graph, and test it on randomly generated graphs.