zbMATH — the first resource for mathematics

Algorithms for efficient filtering in content-based multicast. (English) Zbl 1006.68561
Meyer auf der Heide, Friedhelm (ed.), Algorithms - ESA 2001. 9th annual European symposium, Århus, Denmark, August 28-31, 2001. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 2161, 428-439 (2001).
Summary: Content-Based Multicast is a type of multicast where the source sends a set of different classes of information and not all the subscribers in the multicast group need all the information. Use of filtering publish-subscribe agents on the intermediate nodes was suggested by F. Anjum and R. Jain (2000) to filter out the unnecessary information on the multicast tree. However, filters have their own drawbacks like processing delays and infrastructure cost. Hence, it is desired to place these filters most efficiently. An \(O(n^2)\) dynamic programming algorithm was proposed to calculate the best locations for filters that would minimize overall delays in the network [F. Anjum et al. (2001)]. We propose an improvement of this algorithm which exploits the geometry of piecewise linear functions and fast merging of sorted lists, represented by height balanced search trees, to achieve \(O(n\log{n})\) time complexity. Also, we show an improvement of this algorithm which runs in \(O(n\log{h})\) time, where \(h\) is the height of the multicast tree. This problem is closely related to \(p\)-median and uncapacitated facility location over trees. Theoretically, this is an uncapacitated analogue of the \(p\)-inmedian problem on trees as defined by G. Cornuejols et al. (1990).
For the entire collection see [Zbl 0971.00046].
68U35 Computing methodologies for information systems (hypertext navigation, interfaces, decision support, etc.)
90C39 Dynamic programming
90C59 Approximation methods and heuristics in mathematical programming
68R10 Graph theory (including graph drawing) in computer science
Full Text: Link