The Modified CW1 Algorithm For The Degree Restricted Minimum Spanning Tree Problem

. Wamiliana, Louis Caccetta

Abstract


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. 


Keywords


Minimum spanning tree; CW1 Algorithm ; Degree constrained

Full Text:

PDF PDF

References


Boldon, B., N. Deo and N. Kumar, Minimum Weight degree-constrained spanning tree problem: Heuristics and Implementation on an SIMD parallel machine. Parallel Computing, vol. 22, 369 –382, 1996.

Caccetta, L. and S.P. Hill, A Branch and Cut method for the Degree Constrained Minimum Spanning Tree Problem, Networks, vol. 37, pp.74-83, 2001.

Caccetta, L. and Wamiliana, Heuristics Approach For The Degree Constrained Minimum Spanning Tree, Proceeding of The International Modeling and Simulations, pp. 2161-2166, Canberra, 2001.

Caccetta L. and Wamiliana,2004. “A First Level Tabu Search Method for the Degre Constrained Minimum Spanning Tree”, Journal of Quantitative Methods, Vol.1 No.1, pp. 20-32.

Christofides, N., Worst-case Analysis of a New Heuristic for the Traveling Salesman Problem, Carnegy-Mellon University, Pittsburgh, USA, 1976.

Deo N. and N. Kumar, Computation of Constrained Spanning Trees: A Unified Approach. Network Optimization (Lecture Notes in Economics and Mathematical Systems, Editor: Panos M. Pardalos, et al.), Springer-Verlag, Berlin, Germany, pp. 194 – 220, 1997.

Garey, M.R., and D.S. Johnson, Computers and Intractability, A Guide to the Theory of NP-Completeness. Freemann, San Francisco, 1979.

Gavish, B., Topological Design of Centralized Computer Networks Formulations and Algorithms. Networks vol. 12, pp.355 –377, 1982. pp.111 – 134,1995.

Held, M. and R.M. Karp. The traveling salesman problem and minimum spanning trees. Operation Research, vol. 18, pp.1138-1162, 1970. Held, M. and R.M. Karp. The traveling salesman problem and minimum spanning trees. Part II. Mathematical Programming, vol.1, pp.6-25, 1971.

Krishnamoorthy, M., A.T. Ernst, and Y.M., Sharaiha Comparison of Algorithms for the Degree Constrained Minimum Spanning Tree. Journal of Heuristics, Vol. 7 no. 6, pp. 587 – 611, 2001.

Narula,S.C., and C.A. Ho , Degree-Constrained Minimum Spanning Tree. Computer and Operation Research , vol. 7, pp.239-249, 1980.

Prufer, H., Neuer beweis eines satzes über Permutationen. Arch. Math. Phys, vol. 27, pp.742-744, 1918.

Savelsbergh,M., and T. Volgenant, Edge Exchange in The Degree- Constrained Minimum Spanning Tree. Computer and Operation Research 12, pp.341-348, 1985.

Volgenant A., and R. Jonker, A branch and bound algorithm for the traveling salesman problem based on the 1–tree relaxaEuropean Journal of Operational Research, vol. 9, pp. 83-89, 1982

Volgenant, A., A Lagrangean Approach to The Degree-Constrained Minimum Spanning Tree Problem. European Journal Of Operational Research vol. 39, pp.325 - 331, 1989.

Wamiliana, The Modified Penalty Methods for The Degree Constrained Minimum Spanning Tree Problem, Jurnal Sains dan Teknologi, pp.1-12, Vol. 8, 2002.

Wamiliana and Caccetta, 2003. “Tabu Search Based Heuristics for the Degree Constrained Minimum Spanning Tree Problem”, Proceeding of South East Asia Mathematical Society Conference, pp. 133-140.

Wamiliana, 2004. Combinatorial Methods for The Degree Constrained Minimum Spanning Tree Problem, Doctoral Thesis, Dept. of Mathematics and Statistics, Curtin University of Technology.

Zhou, G., and M. Gen, A Note on Genetic Algorithms for Degree Constrained Spanning Tree Problems. Network vol. 30, pp.91 – 95, 1997.


Refbacks

  • There are currently no refbacks.


International Conference on Engineering and Technology Development (ICETD)
Bandar Lampung University
ISSN: 2301-5690