• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

Article

A tolerance-based heuristic approach for the weighted independent set problem

Journal of Combinatorial Optimization. 2015. Vol. 29. No. 2. P. 433-450.
Goldengorin B., Malyshev D., Pardalos P. M., Zamaraev V. A.

The notion of a tolerance is a helpful tool for designing approximation and exact algorithms for solving combinatorial optimization problems. In this paper we suggest a tolerance-based polynomial heuristic algorithm for the weighted independent set problem. Several computational experiments show that our heuristics works very well on graphs of a small density