Exact Exponential-Time Algorithms for NP-hards Problems on Graphs and Hypergraphs - Archive ouverte HAL Access content directly
Theses Year : 2014

Exact Exponential-Time Algorithms for NP-hards Problems on Graphs and Hypergraphs

Algorithmes exacts et exponentiels pour les problèmes NP-difficiles sur les graphes et hypergraphes

(1)
1

Abstract

In this thesis, we are interested in the exact computation of np-hard problems on graphs and hypergraphs. Firstly, we study several variants of colorings. Those variants appear harder than the famous chromatic number problem, by adding difficulty in recognizing the color classes, or more often by introducing various relationships between them. Then we link to problems of transversals in hypergraphs. More precisely, we are interested in enumerating minimal transversals in bounded ranked hypergraphs. Besides the exact computation, we are also interested in fixed parameter tractability. For this area, we study two optimization versions of the famous square root of graphs problem. Finally, we will be interested in solving other problems of graphs related to colorings, or in order to compare efficiencies of algorithms depending on the memory space available. In this thesis, we will apply most of major techniques in designing exact exponential algorithms. The main techniques we use are dynamic programming, inclusion-exclusion, branching, or measure and conquer
Dans cette thèse, nous nous intéressons à la résolution exacte de problèmes NP-difficiles sur les graphes et les hypergraphes. Les problèmes que nous étudions regroupent dans un premier temps des variantes du problème classique du nombre chromatique. Les variantes de ce problème se distinguent par la difficulté introduite par les relations entre les classes de couleurs, ou la difficulté de reconnaissance des classes de couleurs elles-mêmes. Puis nous ferons le lien avec les problèmes de transversaux sur les hypergraphes. Plus particulièrement, il s’agira de s’intéresser à l’énumération de transversaux minimaux dans un hypergraphe de rang borné. Outre la résolution exacte, nous nous intéressons à la résolution à paramètre fixe. Le problème de racine carrée de graphe est un problème important en théorie des graphes. Nous proposons et montrons la solubilité à paramètre fixe de deux problèmes d’optimisation reliés. Finalement, nous nous intéresserons à la résolution de problèmes de graphe, soit en lien avec les problèmes de colorations, soit pour montrer les performances possibles de différents algorithmes en fonction de l’espace mémoire disponible. Dans cette thèse, nous aurons à cœur d’appliquer judicieusement la grande majorité des techniques essentielles en algorithmique exacte exponentielle. Principalement, nous appliquerons la programmation dynamique ou le principe d’inclusion-exclusion pour les problèmes de coloration. La technique de programmation dynamique se retrouvera pour d’autres problèmes de cette thèse, aux côtés d’autres méthodes comme la technique de branchement ou de mesurer et conquérir
Fichier principal
Vignette du fichier
DDOC_T_2014_0336_COCHEFERT.pdf (1.63 Mo) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

tel-01751574 , version 1 (29-03-2018)

Identifiers

  • HAL Id : tel-01751574 , version 1

Cite

Manfred Cochefert. Algorithmes exacts et exponentiels pour les problèmes NP-difficiles sur les graphes et hypergraphes. Autre [cs.OH]. Université de Lorraine, 2014. Français. ⟨NNT : 2014LORR0336⟩. ⟨tel-01751574⟩
73 View
974 Download

Share

Gmail Facebook Twitter LinkedIn More