• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Thèses
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Thèses
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail

Algorithmes exponentiels pour la résolution exacte et approchée de problèmes NP-difficiles

Bourgeois, Nicolas (2009), Algorithmes exponentiels pour la résolution exacte et approchée de problèmes NP-difficiles, doctoral thesis prepared under the supervision of Paschos, Vangelis, Université Paris Dauphine, 241 p.

View/Open
These_Bourgeois.pdf (1.513Mb)
Type
Thèse
Date
2009
Pages
241
Metadata
Show full item record
Author(s)
Bourgeois, Nicolas
Under the direction of
Paschos, Vangelis
Abstract (FR)
Cette thèse se situe à l'interface entre deux branches de la théorie de la complexité, la résolution exacte et l'approximation polynomiale. Nous développons dans un premier temps des algorithmes modérément exponentiels, capables de résoudre des problèmes fondamentaux de théorie des graphes (stable maximum, stable dominant mi-nimal, clique dominante, quasi-stable) de façon plus rapide que ceux existant jusqu'ici. Surtout, nous introduisons la notion d' approximation exponentielle , et exhibons des algorithmes exponentiels à garantie de performance plus rapides que les algorithmes exacts pour une large variété de problèmes classiques, parmi lesquels : stable maximum, domination, coloration de sommets ou d'arêtes, voyageur de commerce, arbre de Steiner. . .
Abstract (EN)
This thesis is a junction between two fields of complexity theory, namely exact computation and efficient approximation.We first design faster exponential algorithms for several NP-hard problems (maximum independent set, minimum independent dominating set, dominating clique, quasi independent set). Moreover, we introduce the "moderately exponential approximation" field, displaying fast (though exponential) approximation algorithms for many classical graph problems, such as : independent set, dominating set, edge and vertex coloring, traveling salesman, Steiner tree. . .
Subjects / Keywords
Optimisation combinatoire; Algorithmes; Théorie des graphes

Related items

Showing items related by title and author.

  • Thumbnail
    Algorithmes et Intractabilité de Certains Problèmes de Domination NP-difficiles avec Structure Privée 
    Dublois, Louis (2021-07-01) Thèse
  • Thumbnail
    An Introduction to Exponential Time Exact Algorithms for Solving NP-hard Problems 
    Paschos, Vangelis; Escoffier, Bruno; Bourgeois, Nicolas (2011) Chapitre d'ouvrage
  • Thumbnail
    Problèmes NP-difficiles : approximation modérément exponentielle et complexité paramétrique 
    Tourniaire, Emeric (2013-06)
  • Thumbnail
    Approximation polynomiale des problèmes NP-difficiles : optima locaux et rapport différentiel 
    Toulouse, Sophie; Paschos, Vangelis; Monnot, Jérôme (2003) Ouvrage
  • Thumbnail
    Exact and superpolynomial approximation algorithms for the densest k-subgraph problem 
    Bourgeois, Nicolas; Giannakos, Aristotelis; Lucarelli, Giorgio; Milis, Ioannis; Paschos, Vangelis (2017) Article accepté pour publication ou publié
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo