Skip to Main content Skip to Navigation
Theses

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 :
Theses
Complete list of metadatas

Cited literature [186 references]  Display  Hide  Download

https://hal.univ-lorraine.fr/tel-01751574
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

File

DDOC_T_2014_0336_COCHEFERT.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : tel-01751574, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

72

Files downloads

757