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

#### Abstract

#### Keywords

#### 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.