From fbc51cdfb7b49a3210203a1dcf8e36889162ce43 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Fri, 7 Mar 2008 19:47:56 +0100 Subject: [PATCH] More on Kolmos's algorithm. --- adv.tex | 41 ++++++++++++++++++++++++++++++++++++++++- 1 file changed, 40 insertions(+), 1 deletion(-) diff --git a/adv.tex b/adv.tex index 3ecfdf7..3a174c8 100644 --- a/adv.tex +++ b/adv.tex @@ -576,7 +576,7 @@ record the order in which the subtrees have been merged in another tree~$B(T)$. The queries on~$T$ can be then easily translated to queries on~$B(T)$. \defn -For a~weighted tree~$T$ we define its \df{Bor\o{u}vka tree} $B(T)$ which records +For a~weighted tree~$T$ we define its \df{Bor\o{u}vka tree} $B(T)$ as a~rooted tree which records the execution of the Bor\o{u}vka's algorithm run on~$T$. The leaves of $B(T)$ are exactly the vertices of~$T$, every internal vertex~$v$ at level~$i$ from the bottom corresponds to a~component tree~$C(v)$ formed in the $i$-th phase of the algorithm. When @@ -668,6 +668,45 @@ of each of the new paths, the reconstruction of answers to the original queries is then trivial. \qed +\para +We will now describe a~simple variant of the depth-first search which finds the +maximum-weight edges for all query paths. + +For every edge~$e=uv$, we consider the set $Q_e$ of all query paths containing~$e$. +The vertex of a~path which is closer to the root will be called its \df{top,} +the other vertex its \df{bottom.} +We define arrays $T_e$ and~$H_e$ as follows: $T_e$ contains +the tops of the paths in~$Q_e$ in order of their increasing depth (we +will call them \df{active tops} and each of them will be stored exactly once). For +each active top~$t=T_e[i]$, the $H_e[i]$ is defined as the heaviest edge of the path $T[v,t]$. +As for every~$i$ the path $T[v,T_e[i+1]]$ is contained within $T[v,T_e[i]]$, +the edges in~$H_e$ must have non-increasing weights: $w(H_e[i+1]) \le +w(H_e[i])$. + +The algorithm constructs the $T_e$'s and $H_e$'s recursively. We assume that the +root has a~parent edge~$r$ and we define $T_r$ and~$H_r$ as empty arrays (no query +path contains~$r$). When we arrived to a~vertex~$u$ via an~edge~$p$ from its parent, +we visit each son~$v$ of~$u$ and we calculate $T_e$ and~$H_e$ for the edge $e=uv$ +from $T_p$ and~$H_p$: + +\itemize\ibull +\:First we remove all tops which are no longer contained in paths crossing the +current edge~$e$. +%For example, we can keep a~use count for every active top and +%decrease counters of the tops of all paths whose bottom is~$u$. + +\:Then we update the heaviest edges for all tops. The new edge~$e$ will replace +all lighter edges in $H_p$. Since $H_p$ is sorted, we can use binary search +to locate the boundary between lighter and heavier edges in it. + +\:Finally we have to add~$u$ as a~new top of there is a~query path which has~$u$ +at its top and its bottom lies anywhere in the subtree rooted at~$v$. +\endlist + +So far, we will be interested in minimizing only the number of comparisons of +edge weights, so we will postpone the exact implementation of the first and the +third step for a~while. + \FIXME{GHT} -- 2.39.5