| Popis: |
One paradigm for optimizing the efficiency of solutions to instances of a difficult problem is to factor the problem into subcases and to optimize the solution for each subcase. Although an optimal solution for the general problem may not be found by this approach, near optimal solutions may be found for many particular instances. This is the approach illustrated by the following problem domain. When designing a network (communication, computing etc.) it may be necessary to impose the following constraint: Given N and M with N < M, for each path from node (u) to node (v) of length M, there must exist a path from (u) to (v), passing through a subset of the same intermediate nodes, of length N. All paths are simple, thus may not pass through a given node more than once. This is essentially the definition of an (M, N)-transitive digraph. A natural question arises: Given a digraph, G, which may not be (M, N)-transitive, how may the minimum (or near minimum) number of edges be added to ensure that it has this property? (i. e. How may the (M, N)-transitive closure be computed?) An algorithm which answers this question for any digraph has been developed and is provided here, but the algorithm requires exponential time complexity in r, the number of nodes of the digraph. However, for many special cases (including, for any M and N, the computation of (M, 1)-transitive closures and all (M, N)-transitive closures on acyclic digraphs) more efficient, polynomial-time, specialized algorithms have been developed and are provided here. All algorithms have been implemented and tested using DEC Ada on a VAX8650. Comparative tests illustrating the time required to run each of the applicible algorithms have been run and the results are summarized. |
