From c78f73fe35f6e307261d50acd2ab722832deabfe Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Tue, 4 Mar 2008 16:57:04 +0100 Subject: [PATCH] Graphs with sorted weights. --- PLAN | 2 -- adv.tex | 15 ++++++++++++++- mst.tex | 2 +- 3 files changed, 15 insertions(+), 4 deletions(-) diff --git a/PLAN b/PLAN index f0c63b4..6383397 100644 --- a/PLAN +++ b/PLAN @@ -50,7 +50,6 @@ Spanning trees: - \cite{pettie:onlineverify} online lower bound - mention Steiner trees - mention matroids -- sorted weights - mention disconnected graphs - Euclidean MST - Some algorithms (most notably Fredman-Tarjan) do not need flattening @@ -67,7 +66,6 @@ Models: - add more context from thorup:aczero, also mention FP operations - refs on Cartesian trees - update notation.tex -- iteration of Q-Heaps Ranking: diff --git a/adv.tex b/adv.tex index f50821d..730e955 100644 --- a/adv.tex +++ b/adv.tex @@ -522,11 +522,24 @@ MST of a~graph with integer edge weights can be found in time $\O(m)$ on the Wor We will combine the Iterated Jarn\'\i{}k's algorithm with the Q-heaps from section \ref{qheaps}. We modify the first pass of the algorithm to choose $t=\log n$ and use the Q-heap tree instead of the Fibonacci heap. From Theorem \ref{qh} and Remark \ref{qhtreerem} we know that the -operations on the Q-heap tree run in constant time, so the whole first phase takes time~$\O(m)$. +operations on the Q-heap tree run in constant time, so the modified first phase takes time~$\O(m)$. Following the analysis of the original algorithm in the proof of Theorem \ref{itjarthm} we obtain $t_2\ge 2^{t_1} = 2^{\log n} = n$, so the algorithm stops after the second phase. \qed +\para +We can also use this technique if the edge weights are not integers, but they +are already sorted. We already knew that the Kruskal's algorithm runs in time +$\O(m\alpha(n))$ in such cases (Theorem \ref{kruskal}), but we can do better: + +\corn{MST for graphs with sorted edges} +For a~graph with edges already sorted by their weights, we can find +the MST in time $\O(m)$ on the Word-RAM. + +\proof +We renumber the weights to $1,\ldots,m$, which does not change the MST +(Lemma \ref{mstiso}), and find the MST using the previous theorem. + \rem Gabow et al.~\cite{gabow:mst} have shown how to speed up the Iterated Jarn\'\i{}k's algorithm to~$\O(m\log\beta(m,n))$. They split the adjacency lists of the vertices to small buckets, keep each bucket diff --git a/mst.tex b/mst.tex index de4ffa9..866bcc1 100644 --- a/mst.tex +++ b/mst.tex @@ -463,7 +463,7 @@ structure would be sufficient, as long as it has $\O(\log n)$ amortized complexi per operation. For example, we can label vertices with identifiers of the corresponding components and always recolor the smaller of the two components. -\thm +\thm\id{kruskal}% Kruskal's algorithm finds the MST of a given graph in time $\O(m\log n)$ or $\O(m\timesalpha(n))$ if the edges are already sorted by their weights. -- 2.39.5