
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
View/ Open
Type
Communication / ConférenceDate
2008Conference title
Second International Conference on Combinatorial Optimization and Applications (COCOA'08)Conference date
2008-08Conference city
St John'sConference country
CanadaBook title
Combinatorial Optimization and Applications Second International Conference, COCOA 2008, St. John's, NL, Canada, August 21-24, 2008, ProceedingsBook author
Yang, Boting; Du, Ding-Zhu; Wang, Cao AnPublisher
Springer
Series title
Lecture Notes in Computer ScienceSeries number
5165Published in
Berlin
ISBN
978-3-540-85096-0
Number of pages
480Pages
139-148
Publication identifier
Metadata
Show full item recordAbstract (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 / Keywords
GraphsRelated items
Showing items related by title and author.
-
Murat, Cécile; Paschos, Vangelis (2006) Document de travail / Working paper
-
Paschos, Vangelis; Murat, Cécile (2010) Article accepté pour publication ou publié
-
Paschos, Vangelis; Murat, Cécile (2002) Article accepté pour publication ou publié
-
Murat, Cécile; Escoffier, Bruno; Della Croce, Federico; Bourgeois, Nicolas; Paschos, Vangelis (2009) Article accepté pour publication ou publié
-
Gabrel, Virginie; Moulet, Alain; Murat, Cécile; Paschos, Vangelis (1997) Article accepté pour publication ou publié