• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail

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
cahierLamsade236.pdf (418.8Kb)
Type
Communication / Conférence
Date
2008
Conference title
Second International Conference on Combinatorial Optimization and Applications (COCOA'08)
Conference date
2008-08
Conference city
St John's
Conference country
Canada
Book title
Combinatorial Optimization and Applications Second International Conference, COCOA 2008, St. John's, NL, Canada, August 21-24, 2008, Proceedings
Book author
Yang, Boting; Du, Ding-Zhu; Wang, Cao An
Publisher
Springer
Series title
Lecture Notes in Computer Science
Series number
5165
Published in
Berlin
ISBN
978-3-540-85096-0
Number of pages
480
Pages
139-148
Publication identifier
http://dx.doi.org/10.1007/978-3-540-85097-7_13
Metadata
Show full item record
Author(s)
Murat, Cécile
Paschos, Vangelis
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 / Keywords
Graphs

Related items

Showing items related by title and author.

  • Thumbnail
    What about future? Robustness under vertex-uncertainty in graph-problems 
    Murat, Cécile; Paschos, Vangelis (2006) Document de travail / Working paper
  • Thumbnail
    Probabilistic optimization in graph-problems 
    Paschos, Vangelis; Murat, Cécile (2010) Article accepté pour publication ou publié
  • Thumbnail
    The probabilistic minimum vertex covering problem 
    Paschos, Vangelis; Murat, Cécile (2002) Article accepté pour publication ou publié
  • Thumbnail
    Probabilistic graph-coloring in bipartite and split graphs 
    Murat, Cécile; Escoffier, Bruno; Della Croce, Federico; Bourgeois, Nicolas; Paschos, Vangelis (2009) Article accepté pour publication ou publié
  • Thumbnail
    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é
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo