Skip to Main content Skip to Navigation

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

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
Document type :
Complete list of metadata

Cited literature [186 references]  Display  Hide  Download
Contributor : Thèses Ul <>
Submitted on : Thursday, March 29, 2018 - 1:21:58 PM
Last modification on : Tuesday, April 10, 2018 - 1:26:58 AM


Files produced by the author(s)


  • HAL Id : tel-01751574, version 1



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⟩



Record views


Files downloads