An optimal time algorithm for finding a maximum weight independent set in a tree
From MaRDI portal
Publication:1107326
DOI10.1007/BF01934098zbMath0652.68077OpenAlexW1970602728MaRDI QIDQ1107326
Publication date: 1988
Published in: BIT (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01934098
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Dynamic programming (90C39)
Related Items (8)
The reduction of computation times of upper and lower tolerances for selected combinatorial optimization problems ⋮ Efficient computation of tolerances in the weighted independent set problem for trees ⋮ New results in two identical machines scheduling with agreement graphs ⋮ Maximum weight t-sparse set problem on vector-weighted graphs ⋮ A tolerance-based heuristic approach for the weighted independent set problem ⋮ A new distributed approximation algorithm for the maximum weight independent set problem ⋮ Layered graphs: applications and algorithms ⋮ An algorithm for the dominator chromatic number of a tree
Cites Work
This page was built for publication: An optimal time algorithm for finding a maximum weight independent set in a tree
