Steiner forests on stochastic metric graphs
Paschos, Vangelis; Telelis, Orestis; Zissimopoulos, Vassilis (2007), Steiner forests on stochastic metric graphs, in 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
TypeCommunication / Conférence
Conference titleFirst International Conference on Combinatorial Optimization and Applications (COCOA'07)
Book titleCombinatorial Optimization and Applications First International Conference, COCOA 2007, Xi'an, China, August 14-16, 2007, Proceedings
Book authorDress, Andreas; Xu, Yinfeng; Zhu, Binhai
Series titleLecture Notes in Computer Science
Number of pages390
MetadataShow full item record
Abstract (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.
Subjects / Keywordsapproximation; Algorithms; Steiner forests; Graphs
Showing items related by title and author.