2B-1
On the complexity of minimum topic-connected overlay problems
○和田幸一（名工大），Juraj Hromkovic（ETH Zurich, Swizerland），泉 泰介（名工大），小野廣隆（九大），Steinova Monika（ETH Zurich, Swizerland）
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, for short) has been investigated:
Given a set of t topics and a collection of n users together with the lists of topics they are intersted in, the aim is to collect these users to a network by a minimum number of edges such that every graph induced by users intersted in a common topic is connected.
In this paper, we consider the complexity of Min-TCO.