Title: Parallel approximation algorithms for minimum routing cost spanning tree

Authors: Kun Chen; Yung En Hsieh; Ping Jung Lu

Addresses: Department of Computer Science and Information Engineering, National Taiwan University, No. 1, Sec. 4, Roosevelt Rd., Taipei 10617, Taiwan ' Department of Computer Science and Information Engineering, National Taiwan University, No. 1, Sec. 4, Roosevelt Rd., Taipei 10617, Taiwan ' Department of Computer Science and Information Engineering, National Taiwan University, No. 1, Sec. 4, Roosevelt Rd., Taipei 10617, Taiwan

Abstract: With the popularity of internet, more and more data is transferred in the network. With the enormous information, the network bandwidth is still a bottleneck. The internet must provide high quality of service to ensure that the information can be transferred fluently. There are some common factors that can affect the quality of services, such as delay time, building cost, routing cost, loss probability, and bandwidth. Estimation of some factors, such as building cost, can be solved in polynomial time, but the estimations of other factors, such as finding the minimum routing cost spanning tree (MRCT), are NP-hard problems. In this paper, we focus on improving two MRCT approximation algorithms (2 and 15/8 approximation) with parallel-computing methods and obtain the impressive experiment results with reduced calculation time.

Keywords: minimum spanning tree; MST; minimum routing cost spanning tree; MRCT; approximation algorithm; parallel algorithm; quality of service; QoS; internet.

DOI: 10.1504/IJCSE.2013.057298

International Journal of Computational Science and Engineering, 2013 Vol.8 No.4, pp.336 - 348

Received: 10 Feb 2012
Accepted: 07 May 2012

Published online: 27 Dec 2013 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article