From 57984a5d6172c5e8560410d1ee035ec25e27f3a5 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Mon, 17 Mar 2008 18:52:17 +0100 Subject: [PATCH] Another bugfix. --- mst.tex | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/mst.tex b/mst.tex index 7c533c1..e178d8b 100644 --- a/mst.tex +++ b/mst.tex @@ -546,7 +546,7 @@ the identifier of the component. This takes $\O(m_i)$ time. Flattening is performed by first removing the loops and then bucket-sorting the edges (as ordered pairs of vertex identifiers) lexicographically, which brings parallel edges together. The bucket sort uses two passes with $n_i$~buckets, so it takes -$\O(n_i+m_i)=\O(m)$. +$\O(n_i+m_i)=\O(m_i)$. \qed \thm -- 2.39.2