Abstract
A dynamic programming algorithm that was initially designed to solve simple queries in chain networks (Scheuermann and Gursel 1984) and later extended to solve similar queries in ring networks (Gursel 1986) is introduced. The algorithm, with the objective of minimizing the total volume of data transmission, can be incorporated into heuristic approaches to solve general queries in networks not necessarily completely connected. Given the sizes of the referenced relations under different reduction states as input, the solution is expressed as a sequence of semi-join operations. The time and space complexity of the algorithm is known to be 0(n ) and 0(np respectively. In this paper the time complexity of the algorithm is improved to 0(n) under favorable input conditions.
Recommended Citation
Gursel, Goker, "IMPROVEMENTS ON THE BEST CASE PERFORMANCE OF A DYNAMIC PROGRAMMING ALGORITHM" (1988). ICIS 1988 Proceedings. 28.
https://aisel.aisnet.org/icis1988/28