Sur quelques problèmes d'optimisation de sous-graphes pour les réseaux

Abstract

Cette thèse contribue de plusieurs manières à la littérature existante.Arbres couvrants indépendants dans les réseaux. Kao et al. ont proposé un algorithme pour construire n-1 ISTs de Bn et ont montré que l'algorithme a une efficacité amortie optimale pour la construction d'arbres multiples. En particulier, chaque sommet peut déterminer son parent dans chaque arbre d'extension en temps constant amorti. L'algorithme est exécuté dans une fonction récursive et est donc difficile à paralléliser. Dans cette thèse, nous présentons un algorithme parallèle pour construire n-1 ISTs dans les réseaux Bn de type bubble-sort. Notre approche peut être entièrement parallélisée, c'est-à-dire que chaque sommet peut déterminer son parent dans chaque arbres couvrant en temps constant. De plus, nous montrons que la complexité temporelle totale O(n x n!) de notre algorithme est asymptotiquement optimale, où n est la dimension de Bn et n! est le nombre de sommets du réseau.Problème de k-sous-graphe le plus dense. Nous montrons que pour tout β > 1/2, Δβ-WDkS est NP-difficile. Nous prouvons que Δβ-WDkS peut être approximé à un facteur près 1/2β + (2β-1)/(2β-(2k-3)) pour tout β > 1/2. De plus, nous montrons comment modifier tout algorithme d'approximation α pour Δ-WDkS afin d'obtenir un algorithme d'approximation δα,β pour Δβ-WDkS pour tout 1/2 < β < 1.Surveillance des arêtes d'un graphe en utilisant les distances. Nous montrons que pour un graphe connecté non trivial graphe connecté G d'ordre n, 1 ≤ dem(G) ≤ n-1 avec dem(G) = 1 si et seulement si G est un arbre, et dem(G) = n-1 si et seulement si c'est un graphe complet. Nous calculons la valeur exacte valeur exacte de dem pour les grilles, les hypercubes, et les graphes bipartis complets. Ensuite, nous relions dem à d'autres paramètres standard des graphes. Nous montrons que dem(G) est limité par l'arboricité du graphe, et que dem(G) est limité par l'arboricité du graphe. arboricité du graphe, et supérieurement limitée par son nombre de couvertures de sommets. Nous montrons que Nous montrons que la détermination de dem(G) pour un graphe d'entrée G est un problème NP-complet, même pour les graphes à apex (graphes obtenus à partir d'un graphe planaire en ajoutant un sommet supplémentaire). Il existe un algorithme d'approximation à facteur logarithmique en temps polynomial, cependant il est NP-difficile de calculer une approximation asymptotiquement meilleure, même pour les graphes bipartis de petit diamètre et pour les graphes bipartis subcubiques. Pour de telles instances, le problème est également problème n'est pas non plus traitable à paramètre fixe lorsqu'il est paramétré par la taille de la solution.Problèmes de localisation de hub. Nous étudions les problèmes de localisation des nœuds. Nous classifions les problèmes, et nous présentons les modèles de base pour différentes variations des HLP. En outre, nous passons en revue certains modèles qui n'ont pas été pris en compte dans les articles précédents. En outre, certaines approches de solution sont présentées.