Introduction Reseaux de Manhattan oriente Reseaux de Manhattan dans le plan norme Conclusion et Perspectives

Nicolas Catusse, Victor Chepoi, Karim Nouioua Et Yann Vaxès

Description

bandeau Introduction Reseaux de Manhattan oriente Reseaux de Manhattan dans le plan norme Conclusion et Perspectives Reseaux de Manhattan dans le plan norme et reseaux de Manhattan orientes Nicolas Catusse, Victor Chepoi, Karim Nouioua et Yann Vaxes Laboratoire d'Informatique Fondamentale de Marseille Equipe Algorithmique, Combinatoire et Recherche Operationnelle Faculte des Sciences de Luminy 5 avril 2012

• introduction reseaux de manhattan


• reseaux de manhattan dans le plan norme


• axe des abscisses


• faculte des sciences de luminy


• laboratoire d'informatique fondamentale

Sujets

• Faculté des Sciences de Luminy

Informations

• Publié par: pefav
• Publié le: 01 avril 2012
• Nombre de lectures: 39
• Langue: Français

Extrait

Introduction R´eseaux de Manhattan orient´e R´eseaux de Manhattan dans le plan norm´e Conclusion et Perspectives
R´eseaux de Manhattan dans le plan norm´e
et r´eseaux de Manhattan orient´es
Nicolas Catusse, Victor Chepoi, Karim Nouioua et Yann Vax`es
Laboratoire d’Informatique Fondamentale de Marseille
´Equipe Algorithmique, Combinatoire et Recherche Op´erationnelle
Facult´e des Sciences de Luminy
5 avril 2012
bandeauIntroduction R´eseaux de Manhattan orient´e R´eseaux de Manhattan dans le plan norm´e Conclusion et Perspectives
1 Introduction
2 R´eseaux de Manhattan orient´e
3 R´eseaux de Manhattan dans le plan norm´e
4 Conclusion et Perspectives
bandeauIntroduction R´eseaux de Manhattan orient´e R´eseaux de Manhattan dans le plan norm´e Conclusion et Perspectives
1 Introduction
2 R´eseaux de Manhattan orient´e
3 R´eseaux de Manhattan dans le plan norm´e
4 Conclusion et Perspectives
bandeauIntroduction R´eseaux de Manhattan orient´e R´eseaux de Manhattan dans le plan norm´e Conclusion et Perspectives
R´eseaux g´eom´etriques
R´eseau rectilin´eaire
Les arˆetes sont parall`eles `a l’axe des abscisses ou `a l’axe des ordonn´ees.
bandeauIntroduction R´eseaux de Manhattan orient´e R´eseaux de Manhattan dans le plan norm´e Conclusion et Perspectives
R´eseaux g´eom´etriques
Chemin r´ectilin´eaire
Chemin constitu´e d’arˆetes rectilin´eaires.
bandeauIntroduction R´eseaux de Manhattan orient´e R´eseaux de Manhattan dans le plan norm´e Conclusion et Perspectives
R´eseaux g´eom´etriques
Chemin de Manhattan ou l -chemin1
Chemin constitu´e d’arˆetes rectilin´eaires qui r´ealise la distance l .1
bandeauIntroduction R´eseaux de Manhattan orient´e R´eseaux de Manhattan dans le plan norm´e Conclusion et Perspectives
R´eseaux g´eom´etriques
R´eseaux de Manhattan
Tous les sommets sont connect´es par un chemin qui r´ealise la distance l .1
bandeauIntroduction R´eseaux de Manhattan orient´e R´eseaux de Manhattan dans le plan norm´e Conclusion et Perspectives
R´eseaux g´eom´etriques
R´eseaux de Manhattan minimum
R´eseau de Manhattan dont la longueur est minimum.
Recherche d’un 1-spanner optimal de la grille de Hanan.
bandeauIntroduction R´eseaux de Manhattan orient´e R´eseaux de Manhattan dans le plan norm´e Conclusion et Perspectives
´Etat de l’art des r´eseaux de Manhattan minimaux
3[1999] Gudmundsson, Levcopoulos et Narasimhan→ facteur 4 en O(n ) et
facteur 8 en O(nlogn)
→ Existe-t-il un algorithme d’approximation de facteur 2?
→ Quel est le statut de complexit´e?
3[2002] Kato, Imai et Asano→ facteur 2 en O(n ) preuve incompl`ete
[2005] Chepoi, Nouioua et Vax`es→ facteur 2 par programmation lin´eaire
[2005] Nouioua→ facteur 2 en O(nlogn)
[2005] Seibert et Unger→ facteur 1.5 contre exemple
[2006] Benkert, Wolff, Shirabe et Widmann→ facteur 3 en O(nlogn)
[2008] Fuchs et Schulze→ algorithme simple facteur 3 en O(nlogn)
2[2008] Guo, Sun et Zhu→ facteur 2 en O(n ) et O(nlogn)
[2009] Chin, Guo et Sun→ probl`eme fortement NP-complet
bandeauIntroduction R´eseaux de Manhattan orient´e R´eseaux de Manhattan dans le plan norm´e Conclusion et Perspectives
1 Introduction
2 R´eseaux de Manhattan orient´e
3 R´eseaux de Manhattan dans le plan norm´e
4 Conclusion et Perspectives
bandeau