Annals of Faculty of Computer and Information Sciences, Hosei University
Department of computer science <<Previous Next>>
HOME >> No.7 CONTENTS >> Shietung PENG
Professor
Shietung PENG
Refereed Publications
  1. B-F Wang, S. Peng, H-Y Yu, and S-C Ku, "Efficient Algorithms for a Constrained k-tree Core problem in a Tree Network", Journal of Algorithms, Vol. 59, 2006, pp. 107- 124.
    Abstract - Given a tree T and parameters k and l, a (k,l)-tree core is a sub-tree X of T having k leaves and a diameter less than or equal to l, which minimizes the sum of the weighted distances from all vertices of T to X. In this paper, two efficient algorithms are presented for finding a (k,l)-tree core of T. The (k,l)-tree core problem has an application in distributed database systems.
  2. Yamin Li, Shietung Peng, and Wanming Chu, "An Efficient Algorithm for Finding an Almost Connected Dominating Set of Small Size on Wireless Ad Hoc Networks", Proceedings of the Third IEEE International Conference on Mobile Ad-hoc and Sensor Systems (MASS2006), October 2006. pp. 199-205.
    Abstract - In this paper, we propose an efficient, distributed and localized algorithm for finding an almost connected dominating set of small size on wireless ad hoc networks. Broadcasting and routing based on a connected dominating set (CDS) approach. The efficiency of dominating-set-based broadcasting or routing mainly depends on the overhead in constructing the dominating set and the size of the dominating set. Our algorithm can find a CDS faster and the size of the found CDS is smaller than the previous algorithms proposed in the literature. Although our algorithm cannot guarantee the set found is a CDS but from our simulation results, the probabilities that the found set is a CDS are higher than 99.96% in all cases.
  3. Yamin Li, Shietung Peng, and Wanming Chu, "MCore: A Simple Structure for Effective Overlay Multicast on Mobile Ad Hoc Networks", Proceedings of the IASTED International Conference on Parallel and Distributed Computing and Systems (PDCS-2006), November 2006. pp. 341-346.
    Abstract - Overlay multicast protocol constructs a virtual mesh spanning all nodes of a multicast group and employs standard unicast routing to fulfill multicast functionality on application layer. The advantages of this approach are simplicity and flexibility. However, efficiency and stability are the issues that must be addressed as the size of the multicast group grows in the mobile ad hoc networks. In this paper, we propose an effective structure for overlay multicast to solve these problems. Instead of using a spanning tree on the virtual mesh, we adopt a simple structure called MCore for multicast. An MCore is a path that minimizes the sum of the distances of all vertices to the path plus the length of the path. The MCore is more stable and easier to maintain than the spanning tree in MANET. The simulation results show that our approach handles the flexibility and mobility issues in overlay multicast protocols effectively for large multicast group size.
  4. Shietung Peng and Keiichi Kaneko, "Set-to-set Disjoint Paths Routing in Pancake Graphs," in Proceedings of the 18th IASTED International Conference on Parallel and Distributed Computing and Systems, November 2006, pp. 253-258.
    Abstract - In this paper, we propose an efficient algorithm that finds disjoint paths for set-to-set routing in pancake graphs. For an n-pancake graph, the algorithm can find n-1 disjoint paths of small maximum length with optimal time complexity. That is, the n-1 paths can be constructed in O(n2) time and the maximum length is bounded by (5n/3)+O(1).
  5. Keiichi Kaneko and Shietung Peng, "Disjoint Paths Routing in Pancake Graphs," in Proceedings of the 7th International Conference on Parallel and Distributed Computing, Applications and Technologies, December 2006, pp. 254-259.
    Abstract - In this paper, we propose efficient algorithms that find disjoint paths for node-to-node and node-to-set routing in pancake graphs. For an n-pancake graph, the algorithms can find n-1 disjoint paths of small maximum length with optimal time complexity. That is, the n-1 paths can be constructed in O(n2) time and the maximum length is bounded by (5n/3)+6.
  6. Yamin Li, Shietung Peng, and Wanming Chu, "K-MCore for Multicasting on Mobile Ad Hoc Networks", Proceedings of the Seventh International Conference on Parallel and Distributed Computing, Applications and Technologies (PDCAT'06), December 2006. pp. 109-114.
    Abstract - A k-cluster of a tree includes a single path and k-1 sub-paths growing from that path. A k-MCore is a k-cluster that minimizes the sum of the distances of all vertices to the cluster plus the size of the cluster. This structure is motivated by the applications on overlay multicasting. The overlay multicast protocol constructs a virtual mesh spanning all member nodes of a multicast group. It employs standard unicast routing and forwarding to fulfill multicast functionality. In this paper, we propose effective distributed algorithms for constructing k-MCore on a tree network. The k-MCore is more stable and easier to maintain than the spanning tree in virtual mesh. The simulation results show that our approach handles the flexibility and mobility issues in an overlay multicast protocol effectively, especially when the group size is large.

>PAGE TOP