Efficient computation of tolerances in the weighted independent set problem for some classes of graphs

DOI10.1134/S106456241402029XzbMath1306.05185MaRDI QIDQ461929

Panos M. Pardalos, Dmitriy S. Malyshev

Publication date: 15 October 2014

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

Mathematics Subject Classification ID

Trees (05C05) Dynamic programming (90C39) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Signed and weighted graphs (05C22)

Related Items (1)

The reduction of computation times of upper and lower tolerances for selected combinatorial optimization problems

Cites Work

• Efficient computation of tolerances in the weighted independent set problem for trees
• A linear algorithm for analysis of minimum spanning and shortest-path trees of planar graphs
• Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
• Lower tolerance-based branch and bound algorithms for the ATSP
• Sensitivity analysis for shortest path problems and maximum capacity path problems in undirected graphs
• An addendum on: ``Sensitivity analysis of the optimal assignment
• Sensitivity analysis for minimum Hamiltonian path and traveling salesman problems
• Arc tolerances in shortest path and network flow problems
• Max flows in O(nm) time, or better

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