Wamiliana, Wamiliana and Caccetta, Louis (2013) The Modified CW1 Algorithm For The Degree Restricted Minimum Spanning Tree Problem. International Journal of Engineering and Technology Development, 1 (2). pp. 32-36. ISSN 2337-3180
|
Text
ipi158418_2, IJEST paper.pdf Download (285kB) | Preview |
Abstract
Given edge weighted graph G (all weights are nonnegative), 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 Wamiliana and Caccetta (2003). The results on540 random table problems will be discussed. Keywords— Minimum spanning tree; CW1 Algorithm ; Degree constrained
| Item Type: | Article |
|---|---|
| Subjects: | Q Science > Q Science (General) |
| Divisions: | Fakultas Matematika dan Ilmu Pengetahuan Alam (FMIPA) > Prodi Magister Ilmu Matematika |
| Depositing User: | WAMILIANA |
| Date Deposited: | 18 Aug 2016 04:57 |
| Last Modified: | 18 Aug 2016 04:57 |
| URI: | http://repository.lppm.unila.ac.id/id/eprint/316 |
Actions (login required)
 |
View Item |