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

Article

Efficient Computation of Tolerances in the Weighted Independent Set Problem for Trees

Doklady Mathematics. 2013. Vol. 87. No. 3. P. 368-371.
Goldengorin B. I., Malyshev D., Pardalos P. M.

The notion of a tolerance of an element of a combinatorial optimization problem is often used for stability analysis of an optimal solution and it is a base for design branch-and-bound algorithms solving such problems. In this paper we show that for the weighted independent set problem on trees with n vertices all upper and lower tolerances related to this solution can be computed with O(n) time.