An optimal time algorithm for finding a maximum weight independent set in a tree
The maximum weight independent set problem for a general graph is NP- hard. But for some special classes of graphs, polynomial time algorithms do exist for solving it. Based on the divide-and-conquer strategy, \textit{Sh. Pawagi} [ibid. 27, 170-180 (1987; Zbl 0642.68128)] has presented an O(\(| V| \log | V|)\) time algorithm for solving this problem on a tree. In this paper, we propose an O(\(| V|)\) time algorithm to improve Pawagi's result. The proposed algorithm is based on the dynamic programming strategy and is time optimal within a constant factor.
- An algorithm for finding a maximum weighted independent set in an arbitrary graph
- Maximum weight independent set in trees
- scientific article; zbMATH DE number 1522948
- An efficient algorithm for finding a maximum weight 2-independent set on interval graphs
- Efficient computation of tolerances in the weighted independent set problem for trees
- scientific article; zbMATH DE number 1094324
- An algorithm for the maximum weight independent set problem on outerstring graphs
- A generalized linear time algorithm for an optimal \(k\)-distance dominating set of a weighted tree
- A note on greedy algorithms for the maximum weighted independent set problem
- A linear time algorithm for finding an optimal degree-bounded subtree of an edge-weighted tree
- Maximum weight independent set in trees
- A new distributed approximation algorithm for the maximum weight independent set problem
- A tolerance-based heuristic approach for the weighted independent set problem
- Layered graphs: applications and algorithms
- An algorithm for the dominator chromatic number of a tree
- The reduction of computation times of upper and lower tolerances for selected combinatorial optimization problems
- New results in two identical machines scheduling with agreement graphs
- Make it practical: a generic linear-time algorithm for solving maximum-weightsum problems
- Efficient computation of tolerances in the weighted independent set problem for trees
- scientific article; zbMATH DE number 1522948 (Why is no real title available?)
- Maximum weight t-sparse set problem on vector-weighted graphs
- Mobile agents on chordal graphs: maximum independent set and beyond
This page was built for publication: An optimal time algorithm for finding a maximum weight independent set in a tree
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1107326)
