Hi! I have the following problem regarding MSTs. ↵
↵
Given a **complete** undirected graph $G = (V,E)$ of edges only costing either 1 or 2, find a subset of the edges $|E'|=k$ for some $k$ and vertices $V'$ such that $(V', E')$ form a **tree**, is **connected**, and is of **minimum cost**.↵
↵
The bounds for this problem is that $1 \le n \le 10^3$ and $1 \le k \le n - 1$↵
↵
To me, this is very similar to an MST problem, but running a classic MST algorithm would be slow and I'm trying to do this in $O(|E|)$ time by making use of the **complete** graph property.
↵
Given a **complete** undirected graph $G = (V,E)$ of edges only costing either 1 or 2, find a subset of the edges $|E'|=k$ for some $k$ and vertices $V'$ such that $(V', E')$ form a **tree**
↵
The bounds for this problem is that $1 \le n \le 10^3$ and $1 \le k \le n - 1$↵
↵
To me, this is very similar to an MST problem, but running a classic MST algorithm would be slow and I'm trying to do this in $O(|E|)$ time by making use of the **complete** graph property.
