id: 05498450
dt: a
an: 05498450
au: Murat, Cécile; Paschos, Vangelis Th.
ti: Vertex-uncertainty in graph-problems. (Extended abstract).
so: Yang, Boting (ed.) et al., Combinatorial optimization and applications.
    Second international conference, COCOA 2008, St. John’s, NL, Canada,
    August 21‒24, 2008. Proceedings. Berlin: Springer (ISBN
    978-3-540-85096-0/pbk). Lecture Notes in Computer Science 5165, 139-148
    (2008).
py: 2008
pu: Berlin: Springer
la: EN
cc: 
ut: 
ci: 
li: doi:10.1007/978-3-540-85097-7_13
ab: Summary: 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^{\vert
    V\vert}$ 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.
rv: