Introduction Reseaux de Manhattan oriente Reseaux de Manhattan dans le plan norme Conclusion et Perspectives
101
pages
Français
Documents
2012
Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus
Découvre YouScribe et accède à tout notre catalogue !
Découvre YouScribe et accède à tout notre catalogue !
101
pages
Français
Documents
2012
Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus
- introduction reseaux de manhattan
- reseaux de manhattan dans le plan norme
- axe des abscisses
- faculte des sciences de luminy
- laboratoire d'informatique fondamentale
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
