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 Wamiliana and Caccetta (2003). The results on540 random table problems will be discussed.

Keywords


Minimum spanning tree; CW1 Algorithm ; Degree constrained

Full Text:

PDF

References


Boldon, B., N. Deo and N. Kumar, Minimum Weight degreeconstrained

spanning tree problem: Heuristics and Implementation

on an SIMD parallel machine. Parallel Computing, vol. 22, 369 –

, 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 DegreConstrained 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

TravelingSalesman 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,

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-

, 1970.

Held, M. and R.M. Karp. The traveling salesman problem and

minimum spanning trees. Part II. MathematicalProgramming,

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-

, 1980.

Prufer, H., NeuerbeweiseinessatzesüberPermutationen. 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 Research12, 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-

, 1982

Volgenant, A., A Lagrangean Approach to TheDegree-

Constrained Minimum Spanning Tree Problem. European Journal

Of Operational Researchvol. 39, pp.325 - 331, 1989.

Wamiliana, The Modified Penalty Methods for The Degree

Constrained Minimum Spanning Tree Problem,

JurnalSainsdanTeknologi, pp.1-12, Vol. 8, 2002.

Wamiliana and Caccetta, 2003. “Tabu SearchBased 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 TheDegree 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.