Vertex-uncertainty in graph-problems
Murat, Cécile; Paschos, Vangelis (2008), Vertex-uncertainty in graph-problems, in Yang, Boting; Du, Ding-Zhu; Wang, Cao An, Combinatorial Optimization and Applications Second International Conference, COCOA 2008, St. John's, NL, Canada, August 21-24, 2008, Proceedings, Springer : Berlin, p. 139-148. http://dx.doi.org/10.1007/978-3-540-85097-7_13
TypeCommunication / Conférence
Conference titleSecond International Conference on Combinatorial Optimization and Applications (COCOA'08)
Conference citySt John's
Book titleCombinatorial Optimization and Applications Second International Conference, COCOA 2008, St. John's, NL, Canada, August 21-24, 2008, Proceedings
Book authorYang, Boting; Du, Ding-Zhu; Wang, Cao An
Series titleLecture Notes in Computer Science
Number of pages480
MetadataShow full item record
Abstract (EN)We study a probabilistic model for graph-problems under vertex-uncertainty. We assume that any vertex v i of the input-graph G has only a probability p i to be present in the final graph to be optimized (i.e., the final instance for the problem tackled will be only a sub-graph of the initial graph). Under this model, the original “deterministic” problem gives rise to a new (deterministic) problem on the same input-graph G, having the same set of feasible solutions as the former one, but its objective function can be very different from the original one, the set of its optimal solutions too. Moreover, this objective function is a sum of 2|V| terms, where V is the vertex-set of G; hence, its computation is not immediately polynomial. We give sufficient conditions for large classes of graph-problems under which objective functions of the probabilistic counterparts are polynomially computable and optimal solutions are well-characterized.
Subjects / KeywordsGraphs
Showing items related by title and author.
Murat, Cécile; Escoffier, Bruno; Della Croce, Federico; Bourgeois, Nicolas; Paschos, Vangelis (2009) Article accepté pour publication ou publié
A new single model and derived algorithms for the satellite shots planning problem using graph theory concepts Gabrel, Virginie; Moulet, Alain; Murat, Cécile; Paschos, Vangelis (1997) Article accepté pour publication ou publié