On the approximability and hardness of minimum topic connected overlay and its special instances

In the context of designing a scalable overlay network to support decentralized topic-based pub/sub communication, the Minimum Topic-Connected Overlay problem (Min-TCO in short) has been investigated: given a set of t topics and a collection of n users together with the lists of topics they are inte...

Full description

Saved in:
Bibliographic Details
Published in:Theoretical computer science 2012-04, Vol.429, p.144-154
Main Authors: Hosoda, Jun, Hromkovič, Juraj, Izumi, Taisuke, Ono, Hirotaka, Steinová, Monika, Wada, Koichi
Format: Article
Language:English
Subjects:
Approximation algorithm
formula omitted
Hardness
Topic-connected overlay
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In the context of designing a scalable overlay network to support decentralized topic-based pub/sub communication, the Minimum Topic-Connected Overlay problem (Min-TCO in short) has been investigated: given a set of t topics and a collection of n 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. It is known that Min-TCO is NP-hard and approximable within O(logt) in polynomial time. In this paper, we further investigate the problem and some of its special instances. We give various hardness results for instances where the number of topics in which a user is interested in is bounded by a constant, and also for the instances where the number of users interested in a common topic is a constant. For the latter case, we present a first constant approximation algorithm. We also present some polynomial-time algorithms for very restricted instances of Min-TCO.
ISSN:0304-3975
1879-2294
DOI:10.1016/j.tcs.2011.12.033