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.

The Maximum Weight Independent Set Problem

Given a path graph G=(V, E) where V consists in a set of n vertices v₀, v₁ ... v_n-1 that form a path, each of vertices with its own positive weight w_i, compute a maximum weight independent set of the graph. An independent set is a set of vertices in which none is adjacent to the other.

A Dynamic Programming Approach

The key to finding a dynamic programming algorithm is to identify a small set of subproblems whose solution can be computed using the previous subproblems' solutions.