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

DOI10.1007/BF01934098zbMATH Open0652.68077OpenAlexW1970602728MaRDI QIDQ1107326FDOQ1107326

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

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

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)

Cites Work

• Title not available (Why is that?)
• 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
• Title not available (Why is that?)
• 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)