05793342

j

05793342 Nagy, Marius Locating the median of a tree in real time. Parallel Process. Lett. 19, No. 1, 39-55 (2009). 2009 World Scientific, Singapore EN median problem real time parallelism synergy quality-up

doi:10.1142/S0129626409000055

Summary: 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.