No Access

LOCATING THE MEDIAN OF A TREE IN REAL TIME

MARIUS NAGY

School of Computing, Queen's University, Kingston, Ontario, Canada K7L 3N6, Canada

https://doi.org/10.1142/S0129626409000055Cited by:0 (Source: Crossref)

Abstract

Determining the optimal location of a switching center in a tree network of users is accurately modeled by the median problem. A real-time approach is used in this paper to investigate the dynamics of such a communication network in two cases: (1) a growing tree of nodes associated with equal demand rates, and (2) a stream of corrections that arbitrarily change the demand rates at the nodes. The worst-case analysis performed in both situations clearly demonstrates the importance of parallelism in such real-time paradigms. It is shown that the error generated by the best sequential algorithm in the first case can be arbitrarily large. A synergistic behavior is revealed when the quality-up is investigated in the second case.

Keywords:

References

K. Abrahamsonet al., Journal of Algorithms 10, 287 (1989), DOI: 10.1016/0196-6774(89)90017-5. Crossref, Web of Science, Google Scholar
S. G. Akl, Nonlinearity, maximization and parallel real-time computation, Proceedings of the Twelfth Conference on Parallel and Distributed Computing and Systems (2000) pp. 31–36. Google Scholar
S. G. Akl, Computing and Informatics 21(5), 455 (2002). Web of Science, Google Scholar
S. G. Akl, The Journal of Supercomputing 29(1), 89 (2004), DOI: 10.1023/B:SUPE.0000022574.59906.20. Crossref, Web of Science, Google Scholar
S. G. Akl and S. D. Bruda, Parallel Processing Letters 9, 499 (1999), DOI: 10.1142/S0129626499000463. Link, Google Scholar
S. G. Akl and S. D. Bruda, Parallel real-time cryptography: Beyond speedup II, Proceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications (2000) pp. 1283–1289. Google Scholar
S. G. Akl and S. D. Bruda, International Journal of Computers and their Applications, Special Issue on High Performance Computing Systems 7, 31 (2000). Web of Science, Google Scholar
S. G. Akl and S. D. Bruda, The Journal of Supercomputing 19, 219 (2001), DOI: 10.1023/A:1011179823237. Web of Science, Google Scholar
S. D. Bruda and S. G. Akl, On the data-accumulating paradigm, Proceedings of the Fourth International Conference on Computer Science and Informatics (1998) pp. 150–153. Google Scholar
S. D. Bruda and S. G. Akl, Theory of Computing Systems 33, 85 (2000), DOI: 10.1007/s002249910005. Crossref, Web of Science, Google Scholar
S. D. Bruda and S. G. Akl, Journal of Parallel and Distributed Computing 61, 688 (2001), DOI: 10.1006/jpdc.2000.1707. Crossref, Web of Science, Google Scholar
H. Gazit, G. L. Miller and S.-H. Teng, Optimal tree contraction in an EREW model, Proceedings of the 1987 Princeton Workshop on Algorithm, Architecture and Technology Issues for Models of Concurrent Computation (1987) pp. 139–156. Google Scholar
A. J. Goldman, Transportation Science 5, 212 (1971), DOI: 10.1287/trsc.5.2.212. Crossref, Google Scholar
S. L. Hakimi, Operations Research 12, 450 (1964), DOI: 10.1287/opre.12.3.450. Crossref, Web of Science, Google Scholar
G. Y. Handler and P. Mirchandani , Location on Networks: Theory and Algorithms ( MIT Press , Cambridge, Massachusetts , 1979 ) . Google Scholar
S. R. Kosaraju and A. L. Delcher, Optimal parallel evaluation of tree-structured computation by raking, Proceedings of the Third Aegean Workshop on Computing (1988) pp. 101–110. Google Scholar
B. C. Tansel, R. L. Francis and T. J. Lowe, Management Science 29, 482 (1983), DOI: 10.1287/mnsc.29.4.482. Crossref, Web of Science, Google Scholar