From 49faa00b579415971038e9fe9fafe11e4ca4c86d Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Sun, 27 Apr 2008 22:27:05 +0200 Subject: [PATCH] Corrections to K-best. --- dyn.tex | 19 ++++++++++++++----- 1 file changed, 14 insertions(+), 5 deletions(-) diff --git a/dyn.tex b/dyn.tex index 221472c..c31c63e 100644 --- a/dyn.tex +++ b/dyn.tex @@ -765,15 +765,22 @@ exchange in this sequence therefore obtains~$T_i$ from a~tree of the desired pro \para This lemma implies that the second best spanning tree~$T_2$ differs from~$T_1$ by a~single -edge. It remains to find which exchange it is. Let us consider the exchange +edge exchange. It remains to find which exchange it is. Let us consider the exchange of an~edge $f\in E\setminus T_1$ with an~edge $e\in T_1[f]$. We get a~tree $T_1-e+f$ of weight $w(T_1)-w(e)+w(f)$. To obtain~$T_2$, we have to find~$e$ and~$f$ such that the difference $w(f)-w(e)$ is the minimum possible. Thus for every~$f$, the edge $e$~must be always the heaviest on the path $T_1[f]$. We can now apply the algorithm from Corollary \ref{rampeaks} -to find the heaviest edges (peaks) of all such paths and thus examine all possible choices of~$f$ -in linear time. This implies the following: +and find the heaviest edges (peaks) of all such paths and thus examine all possible choices of~$f$ +in linear time. So we get: \lemma +For every graph~$H$ and a~MST $T$ of~$H$, linear time is sufficient to find +edges $e\in T$ and $f\in H\setminus T$ such that $w(f)-w(e)$ is minimum. + +\nota +We will call this \df{finding the best exchange in $(H,T)$.} + +\cor Given~$G$ and~$T_1$, we can find~$T_2$ in time $\O(m)$. \paran{Third lightest spanning tree}% @@ -808,7 +815,9 @@ on both~$G_1$ and~$G_2$ and find~$T_3$ again in time $\O(m)$. \paran{Further spanning trees}% The construction of auxiliary graphs can be iterated to obtain $T_1,\ldots,T_K$ for an~arbitrary~$K$. We will build a~\df{meta-tree} of auxiliary graphs. Each node of this meta-tree -is assigned a~minor of~$G$ and its minimum spanning tree. The root node contains~$(G,T_1)$, +is assigned a~graph\foot{This graph is always derived from~$G$ by a~sequence of edge deletions +and contractions. It is tempting to say that it is a~minor of~$G$, but this is not true as we +preserve multiple edges.} and its minimum spanning tree. The root node contains~$(G,T_1)$, its sons have $(G_1,T_1/e)$ and $(G_2,T_2)$. When $T_3$ is obtained by an~exchange in one of these sons, we attach two new leaves to that son and we assign to them the two auxiliary graphs derived by contracting or deleting the exchanged edge. Then we find the best @@ -829,7 +838,7 @@ them into the heap. The algorithm is now straightforward and so will be its anal \:$R\=$ a~meta tree whose vertices carry triples $(G',T',F')$. Initially it contains just a~root with $(G,T_1,\emptyset)$. \hfil\break - \cmt{$G'$ is a~minor of~$G$, $T'$~is its MST, and~$F'$ is a~set of edges of~$G$ + \cmt{$G'$ is a~graph, $T'$~is its MST, and~$F'$ is a~set of edges of~$G$ that are contracted in~$G'$.} \:$H\=$ a~heap of quadruples $(\delta,r,e,f)$ ordered on~$\delta$, initially empty. \hfil\break -- 2.39.2