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
TypeArticle accepté pour publication ou publié
Journal nameInternational Transactions in Operational Research
Blackwell Publishing Limited
MetadataShow full item record
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 / KeywordsVertex operator algebras; Mathematical optimization
Showing items related by title and author.