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

## 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.