2
$\begingroup$

I am going through the paper https://pubsonline.informs.org/doi/abs/10.1287/moor.10.4.701 which is A Note on Finding Minimum-Cost Edge-Disjoint Spanning Trees and the authors are James Roskind and Robert E. Tarjan. In it, there is an algorithm to generate an augmenting sequence used in updating edge-disjoint forests.

If $F$ is a forest and $e = \{v, w\}$ is an edge such that $v$ and $w$ are in the same tree of $F$, we define $F(e)$ to be the unique path in $F$ joining $v$ and $w$. If $i$ is any integer, we define $i+ = (i $ mod $k) + 1$. For a given set of edge-disjoint forests $F_1$, $F_2$, $\ldots$, $F_k$ and edges $e_0$ and $e_l$, a swap sequence from $e_0$ to $e_l$ is a sequence of edges $e_0$, $e_1$, . . , $e_l$ such that, for $j \in [0 \ldots l- 1]$, $e_{j+1} \in F_{j+} (e_j)$. The swap sequence is augmenting if $e_0$ is in none of the forests $F_1$, $F_2$, $\ldots$, $F_k$, the endpoints of $e_l$, are in different trees of $F_{l+}$, and the swap sequence is minimal in the sense that there are no two edges $e_{j'}$ and $e_j$, such that $j' > j + 1$ and $e_j' \in F_{j+}$

The definition for an augmenting swap sequence seems very arbitrary to me at the moment, as I am unable to visualize it properly. I do understand what it is saying, but I am not understanding how this definition is well-motivated. An example would be very great in clarifying this

$\endgroup$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.