Maximum Weight Independent Set Problem: Difference between revisions

From NovaOrdis Knowledge Base
Jump to navigation Jump to search
Line 11: Line 11:
=The Maximum Weight Independent Set Problem=
=The Maximum Weight Independent Set Problem=
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=
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.

Revision as of 21:39, 27 October 2021

External

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.