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

DOI10.1134/S106456241402029XMaRDI QIDQ461929zbMATH OpenFDO

Authors Panos M. Pardalos, D. S. Malyshev

Publication date 15 October 2014

Published in Doklady Mathematics (Search for Journal in Brave)

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

Mathematics Subject Classification ID

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

Recommendations

• Efficient computation of tolerances in the weighted independent set problem for trees
• A tolerance-based heuristic approach for the weighted independent set problem
• The exact weighted independent set problem in perfect graphs and related classes
• An efficient algorithm for finding a maximum weight 2-independent set on interval graphs
• The weighted maximum independent set problem in permutation graphs

Cites work

• A linear algorithm for analysis of minimum spanning and shortest-path trees of planar graphs
• An addendum on: ``Sensitivity analysis of the optimal assignment
• Arc tolerances in shortest path and network flow problems
• Efficient computation of tolerances in the weighted independent set problem for trees
• 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
• Max flows in O(nm) time, or better
• Sensitivity analysis for minimum Hamiltonian path and traveling salesman problems
• Sensitivity analysis for shortest path problems and maximum capacity path problems in undirected graphs

Cited in

(7)

• A tolerance-based heuristic approach for the weighted independent set problem
• The reduction of computation times of upper and lower tolerances for selected combinatorial optimization problems
• The exact weighted independent set problem in perfect graphs and related classes
• Improved FPT Algorithms for Weighted Independent Set in Bull-Free Graphs
• Efficient computation of tolerances in the weighted independent set problem for trees
• Maximum weight t-sparse set problem on vector-weighted graphs
• Efficient online sensitivity analysis for the injective bottleneck path problem

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q461929)