Maximum Weight Independent Set Problem

External

• https://www.coursera.org/learn/algorithms-greedy/lecture/t9XAF/wis-in-path-graphs-optimal-substructure
• https://www.coursera.org/learn/algorithms-greedy/lecture/w040v/wis-in-path-graphs-a-linear-time-algorithm
• https://www.coursera.org/learn/algorithms-greedy/lecture/TZgJM/wis-in-path-graphs-a-reconstruction-algorithm

Internal

• Dynamic Programming Algorithms

Overview

This article introduces the maximum weight independent set of a path graph and provides a dynamic programming algorithm to solve it.