Coloration avec préférences : complexité, inégalités valides et vérification formelle

Benoît Robillard 1 Sandrine Blazy 1, 2 Eric Soutif 1
1 CEDRIC - Centre d'études et de recherche en informatique et communications
2 GALLIUM - Programming languages, types, compilation and proofs
Inria Paris-Rocquencourt
Résumé : Nous nous intéressons à un problème de coloration avec préférences minimale CPM dans les graphes triangulés. Cette étude s'inscrit dans le projet CompCert qui a pour objectif la certification, à l'aide de méthodes formelles, d'un compilateur optimisant du langage C. L'une des optimisations du compilateur certifié est l'allocation des registres du processeur. Optimiser cette allocation de registres revient à résoudre le problème CPM auquel nous nous intéressons. Nous montrons un résultat de complexité concernant CPM et proposons l'amélioration d'une méthode de coupes permettant la résolution de ce problème. Ce travail est une jonction entre la recherche opérationnelle et les méthodes formelles, dans la mesure où nous vérifions formellement par ailleurs la résolution du problème en prouvant correct le développement, hormis la recherche effectuée par le solveur dont la vérification consiste à déterminer a posteriori si la solution proposée est bien correcte.
Document type :
Conference papers
Complete list of metadatas
https://hal.inria.fr/inria-00260712
Contributor : Sandrine Blazy <>
Submitted on : Tuesday, March 4, 2008 - 6:17:01 PM
Last modification on : Saturday, February 9, 2019 - 1:25:21 AM
Long-term archiving on : Friday, September 28, 2012 - 10:36:16 AM

File

ROADEF08.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00260712, version 1

Collections

INRIA | INRIA-ROCQ | CEDRIC-CNAM

Citation

Benoît Robillard, Sandrine Blazy, Eric Soutif. Coloration avec préférences : complexité, inégalités valides et vérification formelle. ROADEF'08, 9e congrès de la Société Française de Recherche Opérationnelle et d'Aide à la Décision, ROADEF, Feb 2008, Clermont-Ferrand, France. pp.123-138. ⟨inria-00260712⟩

Export

BibTeX TEI DC DCterms EndNote

Share

Metrics

Record views

327

Files downloads

119

Contact


archive-ouverte@inria.fr