A New Efficient Algorithm for Generating All Minimal Tie-Sets Connecting Selected Nodes in a Mesh-Structured Network

摘要

This paper presents a new, efficient method of enumerating all minimal tie-sets connecting selected nodes in a mesh-structured network. More precisely, it gives a solution of the following problem: given a network modeled by an undirected graph ${rm G}=({rm V},{rm E})$, V, and E being the sets of G''s vertices, and edges, find each minimal tie-set connecting all nodes of ${rm W}={{rm v}_{1},ldots,{rm v}_{rm k}}$ , a subset of V. (Note that for ${rm W}={rm V}$ the sought tie-sets are the spanning trees of G.) This task is fulfilled in two steps. In the first step, the sets ${rm P}_{2},ldots,{rm P}_{rm k}$ are found, where ${rm P}_{rm i}$ is the set of all loop-free paths connecting ${rm v}_{1}$ to ${rm v}_{rm i}$. This can be done by performing a breadth-first search on G. In the second step, a recursive procedure gradually merges the paths belonging to different sets ${rm P}_{rm i}$, and accomplishes the main task in ${rm k}-2$ iterations. Thus, the new method can be named Acyclic Paths Mergence (APM). This method is compared to the well known Backtracking algorithm; all spanning trees of a small graph are found using both approaches, and the APM method proves more efficient. This difference in efficiency is likely to grow with the size of G. Moreover, the similar complexity of the Backtracking, and the Edge Replacement (another “classic&x-n20;1D; algorithm finding all spanning trees in a graph) methods, and wider applicability of the APM method, are additional arguments in favor of the latter.