The design of a scalable? overlay network to support decentralized topic-based publish/subscribe communication is nowadays a problem of a great importance. We investigate here special instances of one such design problem called Minimum Topic-Connected Overlay. (-liven a collection of users together with the lists of topics they are interested in, the aim is to connect these users to a network by a minimum number of edges such that every graph induced by users interested in a common topic is connected. We investigate instances where in addition the number of users interested in a particular topic is bounded by a constant d > 2. It is known that the general Topic-Connected Overlay is Ω(log n) hard to approximate and approximable by a logarithmic factor. For our special instances, we design a one-to-one reduction to special instances of the hitting set problem. This allows us to present the first constant approximation algorithm, the first kernelizat ion and the first nontrivial exact algorithm for the special instances discussed.
展开▼
