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

Article

Efficient Computation of Tolerances in the Weighted Independent Set Problem for Some Classes of Graphs

Doklady Mathematics. 2014. Vol. 89. No. 2. P. 253-256.
Translator: O. Sipacheva.

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 of branch-and-bound algorithms solving such problems. We show in this paper that for the weighted independent set problem and a bipartite graph with n vertices and m edges an optimal solution is computed in O(nm) time and all tolerances with respect to it are computed in O(n^2) time. We design an algorithm that for an interval graph with n vertices and $m$ edges simultaneously computes an optimal weighted independent set and all corresponding tolerances in
O(n+m) time.