Frage

I have the the following problem.

Say we have a graph $G = (V,E)$ where all $e \in E$ have positive weight, and $E$ can be separated in to two disjoint sets $E = A \cup B$. We have to find a spanning tree such that we minimize total weight but also we can only use a maximum of $c$ edges in $B$.

I feel like this is just Prim/Kruskal with an additional condition in the main if condition, but is that correct? I think we can still use a greedy algorithm but do not know how to show correctness.

Keine korrekte Lösung

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit cs.stackexchange
scroll top