Maximum Weight Independent Set Problem: Difference between revisions
| Line 12: | Line 12: | ||
Given a [[Graph_Concepts#Path_Graph|path graph]] G=(V, E) where V consists in a set of n vertices v<sub>0</sub>, v<sub>1</sub> ... v<sub>n-1</sub> that form a path, each of vertices with its own positive weight w<sub>i</sub>, compute a maximum weight [[Graph_Concepts#Independent_Set|independent set]] of the graph. An independent set is a set of vertices in which none is [[Graph_Concepts#Vertex_Adjacency|adjacent]] to the other. | Given a [[Graph_Concepts#Path_Graph|path graph]] G=(V, E) where V consists in a set of n vertices v<sub>0</sub>, v<sub>1</sub> ... v<sub>n-1</sub> that form a path, each of vertices with its own positive weight w<sub>i</sub>, compute a maximum weight [[Graph_Concepts#Independent_Set|independent set]] of the graph. An independent set is a set of vertices in which none is [[Graph_Concepts#Vertex_Adjacency|adjacent]] to the other. | ||
=A Dynamic Programming Approach= | =A Dynamic Programming Approach= | ||
The key to finding a [[Algorithms#Dynamic_Programming_Algorithms|dynamic programming algorithm]] is to identify a small set of subproblems whose solution can be computed using the previous subproblems' solutions. | The key to finding a [[Algorithms#Dynamic_Programming_Algorithms|dynamic programming algorithm]] is to identify a small set of subproblems whose solution can be computed using the previous subproblems' solutions. In this case, we start with the observation that for the full n vertex path graph, we have two situation: | ||
1. v<sub>n-1</sub> belongs to the solution. In this case, v<sub>n-2</sub> does not belong to the solution, by the properties of an independent set, and the maximum weight of the independent set for the graph G<sub>n</sub>, W<sub>n</sub> = w<sub>n-1</sub> + W<sub>n-2</sub>. | |||
Revision as of 21:43, 27 October 2021
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
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 v0, v1 ... vn-1 that form a path, each of vertices with its own positive weight wi, 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. In this case, we start with the observation that for the full n vertex path graph, we have two situation:
1. vn-1 belongs to the solution. In this case, vn-2 does not belong to the solution, by the properties of an independent set, and the maximum weight of the independent set for the graph Gn, Wn = wn-1 + Wn-2.