Write down the dual of your lp formulation


Let G = (V, E) be a connected, undirected graph. For each edge e ∈ E, we have a cost weight ce. The minimum-spanning-tree problem is to find an acyclic subset T ⊆ E that connects all of the vertices and whose total weight c(T ) = 􏰀e∈T ce is minimized.

1. Formulate this problem as a linear program. Show the correctness of your formulation. 

2. Write down the dual of your LP formulation.

Request for Solution File

Ask an Expert for Answer!!
Data Structure & Algorithms: Write down the dual of your lp formulation
Reference No:- TGS0132433

Expected delivery within 24 Hours