Filter Kruskal algorithm (Undirected, General MST Minimum Spanning Tree (MST))

From Algorithm Wiki

Revision as of 08:54, 10 April 2023 by Admin (talk | contribs)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

Jump to navigation Jump to search

Time Complexity

$O(E \log V)$

Space Complexity

$O(E)$ auxiliary? words

(Kruskal-based, with minimal overhead? filtering should only remove edges, and each edge should only require O(1) information)

Description

Approximate?

Exact

Randomized?

No, deterministic

Model of Computation

Word RAM

Year

2009

Reference

https://dl.acm.org/citation.cfm?id=2791225

Retrieved from "https://algorithm-wiki.csail.mit.edu/w/index.php?title=Filter_Kruskal_algorithm_(Undirected,_General_MST_Minimum_Spanning_Tree_(MST))&oldid=46959"