
Steiner forests on stochastic metric graphs
Paschos, Vangelis; Telelis, Orestis; Zissimopoulos, Vassilis (2007), Steiner forests on stochastic metric graphs, dans Dress, Andreas; Xu, Yinfeng; Zhu, Binhai, Combinatorial Optimization and Applications First International Conference, COCOA 2007, Xi'an, China, August 14-16, 2007, Proceedings, Springer : Berlin, p. 112-123. http://dx.doi.org/10.1007/978-3-540-73556-4_14
Voir/Ouvrir
Type
Communication / ConférenceDate
2007Titre du colloque
First International Conference on Combinatorial Optimization and Applications (COCOA'07)Date du colloque
2007-08Ville du colloque
Xi'anPays du colloque
ChineTitre de l'ouvrage
Combinatorial Optimization and Applications First International Conference, COCOA 2007, Xi'an, China, August 14-16, 2007, ProceedingsAuteurs de l’ouvrage
Dress, Andreas; Xu, Yinfeng; Zhu, BinhaiÉditeur
Springer
Titre de la collection
Lecture Notes in Computer ScienceNuméro dans la collection
4616Ville d’édition
Berlin
Isbn
978-3-540-73555-7
Nombre de pages
390Pages
112-123
Identifiant publication
Métadonnées
Afficher la notice complèteRésumé (EN)
We consider the problem of connecting given vertex pairs over a stochastic metric graph, each vertex of which has a probability of presence independently of all other vertices. Vertex pairs requiring connection are always present with probability 1. Our objective is to satisfy the connectivity requirements for every possibly materializable subgraph of the given metric graph, so as to optimize the expected total cost of edges used. This is a natural problem model for cost-efficient Steiner Forests on stochastic metric graphs, where uncertain availability of intermediate nodes requires fast adjustments of traffic forwarding. For this problem we allow a priori design decisions to be taken, that can be modified efficiently when an actual subgraph of the input graph materializes. We design a fast (almost linear time in the number of vertices) modification algorithm whose outcome we analyze probabilistically, and show that depending on the a priori decisions this algorithm yields 2 or 4 approximation factors of the optimum expected cost. We also show that our analysis of the algorithm is tight.Mots-clés
approximation; Algorithms; Steiner forests; GraphsPublications associées
Affichage des éléments liés par titre et auteur.
-
Paschos, Vangelis; Telelis, Orestis; Zissimopoulos, Vassilis (2010) Article accepté pour publication ou publié
-
Paschos, Vangelis; Telelis, Orestis; Zissimopoulos, Vassilis (2007) Document de travail / Working paper
-
Paschos, Vangelis; Pekergin, Ferhan; Zissimopoulos, Vassilis (1993) Article accepté pour publication ou publié
-
Paschos, Stratos; Paschos, Vangelis; Zissimopoulos, Vassilis (2004) Article accepté pour publication ou publié
-
Zissimopoulos, Vassilis; Hifi, Mhand; Paschos, Vangelis (2004) Article accepté pour publication ou publié