Algorithmes exacts et exponentiels sur les graphes : énumération, comptage et optimisation - Université de Lorraine Access content directly
Theses Year : 2012

Exponential and exact algorithms on graphs : enumeration, counting and optimization

Algorithmes exacts et exponentiels sur les graphes : énumération, comptage et optimisation

Abstract

The assumption that many problems do not admit algorithm (exact and deterministic) polynomial ate of the advent of the theory of NP-completeness in the 70s. Since many theories and algorithmic techniques have been developed to solve these problems difficult as efficiently as possible. In this thesis, we focus on exact algorithms weakly exponential. The objective is to obtain algorithms complexity 0 * (c ^ n) where n is the size of the data and one constant c as small as possible
L'hypothèse qu'un grand nombre de problèmes n'admettent pas d'algorithme (exact et déterministe) polynomial date de l'avènement de la théorie de la NP-complétude dans les années 70. Depuis, de nombreuses théories et techniques algorithmiques se sont développées pour résoudre ces problèmes difficiles le plus efficacement possible. Dans cette thèse, nous nous intéressons aux algorithmes exacts faiblement exponentiels. L'objectif est d'obtenir des algorithmes de complexité 0* (c^n) où n est la taille de la donnée et c une Constante la plus faible possible

Domains

Other [cs.OH]
Fichier principal
Vignette du fichier
DDOC_T_2012_0325_COUTURIER.pdf (1.56 Mo) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

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

Identifiers

  • HAL Id : tel-01749404 , version 1

Cite

Jean-François Couturier. Algorithmes exacts et exponentiels sur les graphes : énumération, comptage et optimisation. Autre [cs.OH]. Université de Lorraine, 2012. Français. ⟨NNT : 2012LORR0325⟩. ⟨tel-01749404⟩
63 View
181 Download

Share

Gmail Facebook X LinkedIn More