From a038a6c9f8a8c6e44c9957cde7172441af4a3871 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Wed, 5 Mar 2008 18:37:37 +0100 Subject: [PATCH] Fixes to the special case section. --- adv.tex | 66 +++++++++++++++++++++++++++++---------------------------- 1 file changed, 34 insertions(+), 32 deletions(-) diff --git a/adv.tex b/adv.tex index 007217b..695969e 100644 --- a/adv.tex +++ b/adv.tex @@ -548,7 +548,7 @@ which need careful handling, so we omit the description of this algorithm. \section{Special cases and related problems} Finally, we will focus our attention on various special cases of the minimum -spanning tree problems, which frequently arise in practice. +spanning tree problem which frequently arise in practice. \examplen{Graphs with sorted edges} When the edges are already sorted by their weights, we can use the Kruskal's @@ -566,23 +566,23 @@ A~more practical way is to use the Jarn\'\i{}k's algorithm (\ref{jarnimpl}), but replace the heap by an~array of $U$~buckets. As the number of buckets is constant, we can find the minimum in constant time and hence the whole algorithm runs in time $\O(m)$, even on the Pointer Machine. For large -values of~$U$, we can build a~binary search tree or the van Emde-Boas +values of~$U,$ we can build a~binary search tree or the van Emde-Boas tree (see Section \ref{ramdssect} and \cite{boas:vebt}) on the top of the buckets to bring the complexity of finding the minimum down to $\O(\log U)$ or $\O(\log\log U)$ respectively. \examplen{Graphs with floating-point weights} A~common case of non-integer weights are rational numbers in floating-point (FP) representation. Even in this case we will be able to find the MST in linear time. -The most common representation of binary FP numbers (as specified by the IEEE -standard 754-1985 \cite{ieee:binfp}) has the nice property that when the +The most common representation of binary FP numbers specified by the IEEE +standard 754-1985 \cite{ieee:binfp} has a~useful property: When the bit strings encoding non-negative FP numbers are read as ordinary integers, the order of these integers is the same as of the original FP numbers. We can therefore once again replace the edge weights by integers and use the linear-time integer algorithm. While the other FP representations (see \cite{dgoldberg:fp} for -an~overview) do not have this property, the corresponding integers can be adjusted -in $\O(1)$ time to the format we need. (More advanced tricks of this type been -employed by Thorup in \cite{thorup:floatint} to extend the integer algorithm -for single-source shortest paths to FP numbers.) +an~overview) need not have this property, the corresponding integers can be adjusted +in $\O(1)$ time to the format we need. (More advanced tricks of this type have been +employed by Thorup in \cite{thorup:floatint} to extend his linear-time algorithm +for single-source shortest paths to FP edge lengths.) \examplen{Graphs with bounded degrees} For graphs with vertex degrees bounded by a~constant~$\Delta$, the problem is either @@ -595,30 +595,31 @@ a~function $\pi: E(G)\rightarrow E(G')$ such that $\mst(G) = \pi^{-1}(\mst(G'))$ The graph $G'$ and the embedding~$\pi$ can be constructed in time $\O(m)$. \proof -We show how to eliminate a~single vertex~$v$ of degree $d>3$, the rest -will follow by induction. +We show how to eliminate a~single vertex~$v$ of degree $d>3$ and then apply +induction. Assume that $v$~has neighbors $w_1,\ldots,w_d$. We replace~$v$ and the edges~$vw_i$ -by a~path $v_1v_2\ldots v_d$ and edges~$v_iw_i$. Each edge of the path will receive -weight smaller than all other weights, the other edges will inherit the weights -of the edges $vw_i$ they replace. The edges of the path will therefore lie in the -MST (this is obvious from the Kruskal's algorithm) and as~$G$ can be obtained from -the new~$G'$ by contracting the path, the rest follows from the Contraction lemma +by $d$~new vertices $v_1,\ldots,v_d$, joined by a~path $v_1v_2\ldots v_d$, and +edges~$v_iw_i$. Each edge of the path will receive a~weight smaller than all +original weights, the other edges will inherit the weights of the edges $vw_i$ +they replace. The edges of the path will therefore lie in the MST (this is +obvious from the Kruskal's algorithm) and as~$G$ can be obtained from the +new~$G'$ by contracting the path, the rest follows from the Contraction lemma (\ref{contlemma}). This step can be carried out in time $\O(d)$. As it replaces a high-degree -vertex by vertices of degree~3, the procedure stops in at most~$n$ such +vertex by vertices of degree~3, the whole procedure stops in at most~$n$ such steps, so it takes time $\O(\sum_{v\in V}\deg(v)) = \O(m)$ including the time needed to find the high-degree vertices at the beginning. \qed \examplen{Euclidean MST} -The MST also has its analogies in the realm of geometric algorithms. Suppose +The MST also has its counterparts in the realm of geometric algorithms. Suppose that we have $n$~points $x_1,\ldots,x_n$ in the plane and we want to find the shortest system of segments connecting these points. If we want the segments to -touch only in the given points, this is equivalent to finding a~MST of the -complete graph on the vertices $V=\{v_1,\ldots,v_n\}$ with edge weights -equal to the Euclidean distances. Since the graph is dense, many of the MST +touch only in the given points, this is equivalent to finding the MST of the +complete graph on the vertices $V=\{x_1,\ldots,x_n\}$ with edge weights +defined as the Euclidean distances of the points. Since the graph is dense, many of the MST algorithms discussed run in linear time with the size of the graph, hence in time $\O(n^2)$. @@ -626,14 +627,14 @@ There is a~more efficient method based on the observation that the MST is always a~subgraph of the Delaunay's tesselation for the given points (this was first noted by Shamos and Hoey in~\cite{shamos:closest}). The tesselation is a~planar graph, which guarantees that it has $\O(n)$ edges, -and it is a~dual graph to the Voronoi diagram of the points, which can +and it is a~dual graph of the Voronoi diagram of the given points, which can be constructed in time $\O(n\log n)$ using for example the Fortune's algorithm \cite{fortune:voronoi}. We can therefore reduce the problem to finding the MST of the tesselation for which $\O(n\log n)$ time -is more than enough. +is more than sufficient. This approach fails for non-Euclidean metrics, but in some cases -(in particular for the rectilinear metric) the $\O(n\log n)$ time +(in particular for the rectilinear metric) the $\O(n\log n)$ time bound is also achievable by the algorithm of Zhou et al.~\cite{zhou:nodel} based on the sweep-line technique and the Red rule. For other variations on the geometric MST, see Eppstein's survey paper @@ -641,10 +642,10 @@ variations on the geometric MST, see Eppstein's survey paper \examplen{Steiner trees} The constraint that the segments in the previous example are allowed to touch -each other only in the given points looks artificial and it is is uncommon in -practical applications (including the application on electrical transmission +each other only in the given points looks artificial and it is indeed uncommon in +practical applications (including the problem of designing electrical transmission lines originally studied by Bor\o{u}vka). If we lift this restriction, we get -the problem known under the name Steiner tree.\foot{It is named after the Swiss mathematician +the problem known by the name Steiner tree.\foot{It is named after the Swiss mathematician Jacob Steiner who studied a~special case of this problem in the 19th century.} We can also define it in terms of graphs: @@ -652,9 +653,10 @@ We can also define it in terms of graphs: of \df{mandatory notes} is a~tree~$T\subseteq G$ which contains all the mandatory vertices and its weight is minimum possible. -Finding the Steiner tree has been proven to be NP-hard by Garey and -Johnson \cite{garey:steiner,garey:rectisteiner} in both the graph version -(even for weights $\{1,2\}$) and in the planar version with Euclidean or rectilinear +For $M=V$ the Steiner tree is identical to the MST, but if we allow an~arbitrary +choice of the mandatory vertices, it is NP-hard. This has been proven by Garey and Johnson +\cite{garey:steiner,garey:rectisteiner} for not only the graph version with +weights $\{1,2\}$, but also for the planar version with Euclidean or rectilinear metric. There is a~polynomial approximation algorithm with ratio $5/3$ for graphs due to Pr\"omel and Steger \cite{proemel:steiner} and a~polynomial-time approximation scheme for the Euclidean Steiner tree in an~arbitrary dimension @@ -673,11 +675,11 @@ at least $3/4$. They have also proven an~almost matching lower bound $\Omega(dw\ For the $d$-dimensional Euclidean case, there is a~randomized approximation algorithm by Czumaj et al.~\cite{czumaj:euclidean} which with high probability produces a~spanning tree within relative error~$\varepsilon$ in $\widetilde\O(\sqrt{n}\cdot \poly(1/\varepsilon))$\foot{% -$\widetilde\O(f(n)) = \O(f(n)\cdot\log^{\O(1)} f(n))$ and $\poly(n)=n^{\O(1)}$.} +$\widetilde\O(f) = \O(f\cdot\log^{\O(1)} f)$ and $\poly(n)=n^{\O(1)}$.} queries to a~data structure containing the points. The data structure is expected to answer orthogonal range queries and cone approximate nearest neighbor queries. -There is also $\widetilde\O(n\cdot \poly(1/\varepsilon))$ time approximation -algorithm for MST weight in arbitrary metric spaces by Czumaj and Sohler \cite{czumaj:metric}. +There is also a~$\widetilde\O(n\cdot \poly(1/\varepsilon))$ time approximation +algorithm for the MST weight in arbitrary metric spaces by Czumaj and Sohler \cite{czumaj:metric}. (This is still sub-linear since the corresponding graph has roughly $n^2$ edges.) \endpart -- 2.39.2