Minimum Spanning Tree problem (MST)

Statement

Minimum Spanning Tree problem

Given an undirected graph with weights can you find a spanning tree with minimum weight

Solutions

• Kruskal’s algorithm
  • It takes .
• Prim’s algorithm
  • It takes .

Theory

• Minimum Spanning Tree problem is in NP