Show simple item record

dc.contributor.authorPaschos, Vangelis
dc.contributor.authorMurat, Cécile
dc.date.accessioned2010-01-14T13:02:59Z
dc.date.available2010-01-14T13:02:59Z
dc.date.issued2002
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/2934
dc.language.isoenen
dc.subjectVertex operator algebrasen
dc.subjectMathematical optimizationen
dc.subject.ddc003en
dc.titleThe probabilistic minimum vertex covering problemen
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenAn instance of the probabilistic vertex-covering problem is a pair (G=(V,E),Pr) obtained by associating with each vertex υ[sub i] ∈V an ‘occurrence’ probability p[sub i] . We consider a modification strategy Μ transforming a vertex cover C for G into a vertex cover C[sub I] for the subgraph of G induced by a vertex-set I⊆V. The objective for the probabilistic vertex-covering is to determine a vertex cover of G minimizing the sum, over all subsets I⊆V, of the products: probability of I times C[sub I] . In this paper, we study the complexity of optimally solving probabilistic vertex-covering.en
dc.relation.isversionofjnlnameInternational Transactions in Operational Research
dc.relation.isversionofjnlvol9en
dc.relation.isversionofjnlissue1en
dc.relation.isversionofjnldate2002
dc.relation.isversionofjnlpages19-32en
dc.description.sponsorshipprivateouien
dc.relation.isversionofjnlpublisherBlackwell Publishing Limiteden
dc.subject.ddclabelRecherche opérationnelleen


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record