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

DOI10.1007/BF01934098zbMath0652.68077MaRDI QIDQ1107326

S. H. Smith

Publication date: 1988

Published in: BIT (Search for Journal in Brave)

zbMATH Keywords

dynamic programming; time optimal; maximum weight independent set in trees

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68R10: Graph theory (including graph drawing) in computer science

90C39: Dynamic programming