Efficient computation of tolerances in the weighted independent set problem for trees

DOI10.1134/S1064562413030186zbMath1275.68111OpenAlexW2095545793MaRDI QIDQ378171

Panos M. Pardalos, Dmitriy S. Malyshev, Boris I. Goldengorin

Publication date: 11 November 2013

Published in: Doklady Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1134/s1064562413030186

zbMATH Keywords

dynamic progammingweighted independent set problem

Mathematics Subject Classification ID

Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Dynamic programming (90C39)

Related Items (2)

The reduction of computation times of upper and lower tolerances for selected combinatorial optimization problems ⋮ Efficient computation of tolerances in the weighted independent set problem for some classes of graphs

Cites Work

• An optimal time algorithm for finding a maximum weight independent set in a tree
• Lower tolerance-based branch and bound algorithms for the ATSP
• Sensitivity analysis for shortest path problems and maximum capacity path problems in undirected graphs
• Tolerance-based branch and bound algorithms for the ATSP
• An addendum on: ``Sensitivity analysis of the optimal assignment
• Arc tolerances in shortest path and network flow problems
• An Algorithm for the Three-Index Assignment Problem
• Experimental and Efficient Algorithms

This page was built for publication: Efficient computation of tolerances in the weighted independent set problem for trees