Computer Science – Data Structures and Algorithms
Scientific paper
2011-07-13
Computer Science
Data Structures and Algorithms
20 pages
Scientific paper
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(log t) 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 an 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 constant. For the latter case, we present a ?rst constant approximation algorithm. We also present some polynomial-time algorithms for very restricted instances of Min-TCO.
Hosoda Jun
Hromkovic Juraj
Izumi Taisuke
Ono Horotaka
Steinova Monika
No associations
LandOfFree
On the Approximability and Hardness of Minimum Topic Connected Overlay and Its Special Instances does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with On the Approximability and Hardness of Minimum Topic Connected Overlay and Its Special Instances, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the Approximability and Hardness of Minimum Topic Connected Overlay and Its Special Instances will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-165075