The Modified CW1 Algorithm For The Degree Restricted Minimum Spanning Tree Problem
| Main Authors: | Wamiliana, .; Lampung University, Indonesia, Caccetta, Louis; Curtin University of Technology, Australia |
|---|---|
| Format: | Article info application/pdf eJournal |
| Bahasa: | eng |
| Terbitan: |
Bandar Lampung University (UBL)
, 2012
|
| Subjects: | |
| Online Access: |
http://artikel.ubl.ac.id/index.php/icetd/article/view/75 http://artikel.ubl.ac.id/index.php/icetd/article/view/75/75 http://artikel.ubl.ac.id/index.php/icetd/article/view/75/903 |
Daftar Isi:
- Given edge weighted graph G (all weights are non-negative), The Degree Constrained Minimum Spanning Tree Problem is concerned with finding the minimum weight spanning tree T satisfying specified degree restrictions on the vertices. This problem arises naturally in communication networks where the degree of a vertex represents the number of line interfaces available at a terminal (center). The applications of the Degree Constrained Minimum Spanning Tree problems that may arise in real-life include: the design of telecommunication, transportation, and energy networks. It is also used as a subproblem in the design of networks for computer communication, transportation, sewage and plumbing. Since, apart from some trivial cases, the problem is computationally difficult (NP-complete), a number of heuristics have been proposed. In this paper we will discuss the modification of CW1 Algorithm that already proposed by Wamilia na and Caccetta (2003). The results on540 random table problems will be discussed.