Der-Tsai Lee

We consider the capacitated domination problem, which models a service-requirement assigning scenario and which is also a generalization of the dominating set problem. In this problem, we are given a graph with three parameters defined on the vertex set, which are cost, capacity, and demand. The objective of this problem is to compute a demand assignment of least cost, such that the demand of each vertex is fully-assigned to some of its closed neighbours without exceeding the amount of capacity they provide. In this paper, we provide the first constant factor approximation for this problem on planar graphs, based on a new perspective on the hierarchical structure of outer-planar graphs. We believe that this new perspective and technique can be applied to other capacitated covering problems to help tackle vertices of large degrees.

Design of the next-generation Internet-based services has been an active research topic, which aims at realising a social activity that generates and distributes Web contents. The development of a knowledge portal is a step towards effective scientific collaboration. A knowledge portal site allows research teammates to create and share their knowledge objects. The portal therefore grows in an unlimited and unexpected fashion. In our previous work, we have developed a visualization tool to display the sitemap of a knowledge portal and observe the concept map of group knowledge because: (a) knowledge objects are represented in web pages but a sitemap cannot be prepared to give an outline of the contents in advance; and (b) the developed knowledge objects are associated with conceptual elements defined within the ontology of the knowledge portal. In this paper, we propose an upgraded map generator that can further construct the knowledge relation map on basis of common references. As for the experimental platform of our visualization tools, we chose a locally developed knowledge portal, called Open Computational Problem Solving (OpenCPS) knowledge portal.