Maximum Weight Independent Set Problem: Difference between revisions
Jump to navigation
Jump to search
| Line 7: | Line 7: | ||
* [[Algorithms#Dynamic_Programming_Algorithms|Dynamic Programming Algorithms]] | * [[Algorithms#Dynamic_Programming_Algorithms|Dynamic Programming Algorithms]] | ||
=Overview= | =Overview= | ||
This article introduces the maximum weight [[Graph_Concepts#Independent_Set|independent set]] of a [[Graph_Concepts#Path_Graph|path graph]] and provides a dynamic programming algorithm to solve it. | |||
=The Maximum Weight Independent Set Problem= | =The Maximum Weight Independent Set Problem= | ||
Revision as of 21:18, 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.