Distances entre classes d'isomorphisme de graphes

Diplôme Thèse Distances entre classes d'isomorphisme de graphes fre 1998-07-15 author Nanchen Emmanuel 29834 director Wanner Gerhard 25224 Administration de la faculté des sciences (SIAD) director Coray Daniel 26390 70 10.13097/archive-ouverte/unige:191859 Sc. 3012 Cette thèse définit une famille de distances entre classes d'isomorphisme de graphes au moyen d'une construction originale. Une deuxième partie propose un vaste tour d'horizon des propriétés de cette famille de distances : le Théorème 2.2 fournit un outil, utilisé tout au long de cette thèse, pour déterminer sous certaines conditions la valeur de la distance entre deux graphes. Les Théorèmes 2.11 et suivants décrivent la forme du graphe de distance associé à une distance. Le Théorème 2.24 établit d'importants liens avec des distances étudiées par d'autres auteurs, et le Théorème 2.46 démontre la NP-complétude du problème de décision associé à notre famille de distances. La dernière partie étudie différents algorithmes donnant une valeur approchée de la valeur de la distance entre deux graphes, dont la marche aléatoire, l'algorithme glouton, le recuit-simulé, la méthode tabou et les algorithmes génétiques. De nombreuses illustrations de leurs performances relatives, par des calculs en machine, justifient des directives d'utilisation. Dewey 510 25 Section de mathématiques 11 false 8f134fbe-fba9-4066-abbe-c838496c5d66 Imprimatur Public AOU_Nanchen_imprimatur.pdf 378510 application/pdf 66469e890e74ce076d239fead61dae350a01c5bb0d4ef886e066d692c3921358 3869ad85-ee51-4ec8-a3cc-db3b5d2ba3a9 Thesis Public AOU_Nanchen_thèse.pdf 30346947 application/pdf Restricted 2098-07-15 b10df38a4cc15cd7e1811a512ec44a827a0049bb78fc77b15422eef1be6c0bfc embargoedAccess Faculté des sciences / Section de mathématiques

Title	Published in	Access level	OA Policy	Year	Views	Downloads

Distances entre classes d'isomorphisme de graphes				1998	7	0

Archive ouverte UNIGE

Nanchen, Emmanuel