Complétions d'intervalles minimales
La largeur linéaire et la largeur arborescente ont été introduites par Robertson et Seymour dans leurs travaux sur les mineurs de graphes. De manière informelle, la largeur linéaire (resp. la largeur arborescente) d un graphe mesure l écart entre ce graphe et la classe des chaînes (des arbres). Les...
Zapisane w:
| 1. autor: | |
|---|---|
| Format: | Thèse numérique |
| Język: | Anglais |
| Wydane: |
Villeurbanne :
[CCSD]
2010.
|
| Hasła przedmiotowe: | |
| Dostęp online: | Accès au texte intégral Accès Université d'Orléans |
| Komentarz: |
Description d'après la consultation, 2018-04-26 Titre provenant de l'écran titre Cette édition peut différer de la version de soutenance enregistrée sous le Numéro National de Thèse : 2006ORLE2068 Thèses CCSD |
| Autres localisations: | Voir dans le Sudoc |
| Variante du titre: | Minimal interval completions |
| Edition sous un autre format: | • Complétions d'intervalles minimales, par Karol Suchan, [S.l.], [s.n.], 2006, 1 vol. (112 p.) |
| LEADER | 03219nam a22003257a 4500 | ||
|---|---|---|---|
| 001 | 928097 | ||
| 008 | 180502s2010 xxe ||| |||| 00| 0 eng d | ||
| 009 | PPN226581578 | ||
| 041 | 0 | |a eng |b fre |b eng |f fre |f eng | |
| 084 | |a 004 | ||
| 100 | 1 | |a Suchan, Karol, |d 1979- | |
| 240 | 1 | 0 | |a Minimal interval completions |
| 245 | 1 | 0 | |a Complétions d'intervalles minimales |c par Karol Suchan ; encadrant, M. Ioan Todinca,... |
| 256 | |a Données textuelles | ||
| 260 | |a Villeurbanne : |b [CCSD], |c 2010. | ||
| 500 | |a Description d'après la consultation, 2018-04-26 | ||
| 500 | |a Titre provenant de l'écran titre | ||
| 500 | |a Cette édition peut différer de la version de soutenance enregistrée sous le Numéro National de Thèse : 2006ORLE2068 | ||
| 500 | |a Thèses CCSD | ||
| 502 | |a Texte remanié de. Thèse de doctorat. Informatique. Orléans. 2006 | ||
| 520 | |a La largeur linéaire et la largeur arborescente ont été introduites par Robertson et Seymour dans leurs travaux sur les mineurs de graphes. De manière informelle, la largeur linéaire (resp. la largeur arborescente) d un graphe mesure l écart entre ce graphe et la classe des chaînes (des arbres). Les deux paramètres se sont révélés très puissants de point de vue algorithmique, car de nombreux problèmes NP-difficiles deviennent polynomiaux lorsque l on se restreint à des classes de graphes de largeur linéaire ou de largeur arborescente bornée. Etant donné un graphe G=(V,E) quelconque, un graphe d intervalles H=(V,F) contenant G est appelé complétion d intervalles de G. Calculer la largeur linéaire de G revient à trouver une complétion d intervalles H, tout en minimisant la clique maximum de H. Le problème étant NP-difficile, nous calculerons des complétions d intervalles minimales, où l on demande seulement que l ensemble d arêtes rajoutées F\\E soit minimal par inclusion parmi toutes les complétions possibles. Une approche similaire, à travers les triangulations minimales, est fortement utilisée pour comprendre et calculer la largeur arborescente. Ce mémoire présente nos résultats sur les complétions d intervalles minimales. Nous donnons trois algorithmes calculant une complétion d intervalles minimale, basés sur des approches différentes. Nous présentons également un algorithme calculant une complétion d intervalles propres minimale. Enfin, nous montrons que la largeur linéaire des graphes d intervalles circulaires peut être calculé en temps polynomial. | ||
| 538 | |a Un logiciel capable de lire un fichier au format PDF | ||
| 650 | |a Calcul sur des intervalles | ||
| 650 | |a Algorithmes | ||
| 650 | |a Graphes, Théorie des | ||
| 650 | |a Thèses et écrits académiques | ||
| 776 | 0 | |0 126484228 |t Complétions d'intervalles minimales |f par Karol Suchan |c [S.l.] |n [s.n.] |d 2006 |p 1 vol. (112 p.) | |
| 856 | 4 | |q PDF |u https://tel.archives-ouvertes.fr/tel-00480669 |z Accès au texte intégral | |
| 856 | 4 | |5 452349901:727097954 |u https://ezproxy.univ-orleans.fr/login?qurl=https%3A//tel.archives-ouvertes.fr/tel-00480669 |z Accès Université d'Orléans | |
| 997 | |0 928097 |1 Thèse numérique |a Ressource numérique |b INSA |b ENSA |c 0/Bibliothèque numérique/ |c 1/Bibliothèque numérique/Autre ressource numérique/ | ||