A priori optimization for the probabilistic maximum independent set problem

DOI10.1016/S0304-3975(01)00005-6zbMath0988.68135MaRDI QIDQ5958320

Cécile Murat, Vangelis Th. Paschos

Publication date: 3 March 2002

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

polynomial approximationindependent setNP-hard problemprobabilistic optimization

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Related Items (10)

A survey on combinatorial optimization in dynamic environments ⋮ Probabilistic combinatorial optimization problems on graphs: A new domain in operational research ⋮ The probabilistic minimum dominating set problem ⋮ On the probabilistic min spanning tree problem ⋮ Independence number and the number of maximum independent sets in pseudofractal scale-free web and Sierpiński gasket ⋮ Algorithm to find a maximum 2-packing set in a cactus ⋮ On the probabilistic minimum coloring and minimum \(k\)-coloring ⋮ Probabilistic models for the Steiner Tree problem ⋮ Probabilistic graph-coloring in bipartite and split graphs ⋮ Vertex-Uncertainty in Graph-Problems

Cites Work

• Parallel concepts in graph theory
• A new single model and derived algorithms for the satellite shot planning problem using graph theory concepts
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• Node-weighted graphs having the König-Egerváry property
• Shortest path problems with node failures
• The Probabilistic Minimum Vertex-covering Problem
• A Priori Optimization
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: A priori optimization for the probabilistic maximum independent set problem