Thumbnail

The probabilistic minimum vertex covering problem

Paschos, Vangelis; Murat, Cécile (2002), The probabilistic minimum vertex covering problem, International Transactions in Operational Research, 9, 1, p. 19-32

View/Open
Type
Article accepté pour publication ou publié
Date
2002
Journal name
International Transactions in Operational Research
Volume
9
Number
1
Publisher
Blackwell Publishing Limited
Pages
19-32
Metadata
Show full item record
Author(s)
Paschos, Vangelis
Murat, Cécile
Abstract (EN)
An 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.
Subjects / Keywords
Vertex operator algebras; Mathematical optimization