An optimal time algorithm for finding a maximum weight independent set in a tree

DOI10.1007/BF01934098MaRDI QIDQ1107326zbMATH OpenOpenAlexFDO

Authors S. H. Smith

Publication date 1988

Published in BIT (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf01934098

zbMATH Keywords

dynamic programmingtime optimalmaximum weight independent set in trees

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Dynamic programming (90C39)

Recommendations

• 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

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Maximum weight independent set in trees

Cited in

(11)

• Layered graphs: applications and algorithms
• Maximum weight independent set in trees
• Maximum weight t-sparse set problem on vector-weighted graphs
• A tolerance-based heuristic approach for the weighted independent set problem
• Make it practical: a generic linear-time algorithm for solving maximum-weightsum problems
• An algorithm for the dominator chromatic number of a tree
• New results in two identical machines scheduling with agreement graphs
• The reduction of computation times of upper and lower tolerances for selected combinatorial optimization problems
• scientific article; zbMATH DE number 1522948 (Why is no real title available?)
• Efficient computation of tolerances in the weighted independent set problem for trees
• A new distributed approximation algorithm for the maximum weight independent set problem

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)