DEGREE-CONSTRAINED MINIMUM SPANNING TREE PROBLEM IN STOCHASTIC GRAPH

REFERENCES

• Akbari Torkestani , J. and Meybodi , M. R. “Learning Automata-Based Algorithms for Finding Minimum Weakly Connected Dominating Set in Stochastic Graphs.” International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems 18, no. 6 (2010) : 721 – 58 .
   Google Scholar
• Andrade , R. , Lucena , A. , and Maculan , N. “Using Lagrangian Dual Information to Generate Degree Constrained Spanning Trees.” Discrete Applied Mathematics 154 ( 2006 ): 703 – 17 .
   Google Scholar
• Ausiello , G. , Crescenzi , P. , Gambosi , G. , Kann , V. , Marchetti Spaccamela , A. , and Protasi , M. Approximate Solution of NP-Hard Optimization Problems . Berlin : Springer-Verlag , 1999 .
   Google Scholar
• Bau , Y.-T. , Ho , C.-K. , and Ewe , H.-T. “Ant Colony Optimization Approaches to the Degree-Constrained Minimum Spanning Tree Problem.” Journal of Information Science and Engineering 24 , no. 4 ( 2008 ): 1081 – 94 .
   Google Scholar
• Binh , H. T. T. and Nguyen , T. B. “New Particle Swarm Optimization Algorithm for Solving Degree Constrained Minimum Spanning Tree Problem.” Lecture Notes in Computer Science 5351 ( 2008 ): 1077 – 85 .
   Google Scholar
• Bui , T. N. , Deng , X. , and Zrncic , C. M. “An Improved Ant-Based Algorithm for the Degree-Constrained Minimum Spanning Tree Problem.” IEEE Transactions on Evolutionary Computation ( 2011 ). DOI: 10.1109/TEVC.2011.2125971
   Google Scholar
• Bui , T. N. and Zrncic , C. M. “An Ant-Based Algorithm for Finding Degree-Constrained Minimum Spanning Tree.” Paper presented at the 8th Annual Conference on Genetic and Evolutionary Computation, 8–12 July 2006, Seattle Washington, USA. p. 11–18 .
   Google Scholar
• de Souza , M. C. and Martins , P. “Skewed VNS Enclosing Second Order Algorithm for the Degree Constrained Minimum Spanning Tree Problem.” European Journal of Operational Research 191 ( 2008 ): 677 – 90 .
   Google Scholar
• Doan , M. N. “An Effective Ant-Based Algorithm for the Degree-Constrained Minimum Spanning Tree Problem.” Paper presented at the IEEE Congress on Evolutionary Computation, 25–28 September 2007, Singapore. p. 485–491 .
   Google Scholar
• Ernst , A. T. “A Hybrid Lagrangian Particle Swarm Optimization Algorithm for the Degree-Constrained Minimum Spanning Tree Problem.” Paper presented at the IEEE Congress on Evolutionary Computation, 18–23 July 2010, Barcelona, Spain. p. 1–8.
   Google Scholar
• Garey , M. R. and Johnson , D. S. Computers and Intractability: A Guide to the Theory of NP-Completeness . San Francisco : W.H. Freeman , 1979 .
   Google Scholar
• Goldbarg , E. F. G. , de Souza , G. R. , and Goldbarg , M. C. “Particle Swarm Optimization for the Bi-objective Degree Constrained Minimum Spanning Tree.” Paper presented at the IEEE Congress on Evolutionary Computation, 2006, Vancouver, Canada. p. 420–7 .
   Google Scholar
• Gouveia , L. , Simonetti , L. , and Uchoa , E. “Modeling Hop-Constrained and Diameter-Constrained Minimum Spanning Tree Problems as Steiner Tree Problems over Layered Graphs.” Journal of Mathematical Programming 128, nos. 1–2 (2011): 123–48 .
   Google Scholar
• Gruber , M. , Hemert , J. , and Raidl , G. R. “Neighborhood Searches for the Bounded Diameter Minimum Spanning Tree Problem Embedded in a VNS, EA and ACO.” Paper presented atthe Genetic and Evolutionary Computational Conference (GECCO'2006), 2006, Washington, USA. p. 1187–94 .
   Google Scholar
• Guo , W.-Z. , Gao , H.-L. , Chen , G.-L. , and Yu , L. “Particle Swarm Optimization for the Degree-Constrained MST Problem in WSN Topology Control.” Paper presented at the International Conference on Machine Learning and Cybernetics, 12–15 July 2009, Baoding, China. p. 1793–8 .
   Google Scholar
• Han , L.-X. , Wang , Y. , and Guo , F.-Y. “A New Genetic Algorithm for the Degree-Constrained Minimum Spanning Tree Problem.” Paper presented at the IEEE International Workshop on VLSI Design and Video Technology, 28–30 May, 2005. p. 125–8 .
   Google Scholar
• Hanr , L. and Wang , Y. “A Novel Genetic Algorithm for Degree-Constrained Minimum Spanning Tree Problem.” International Journal of Computer and Network Security 6 , no. 7A ( 2006 ): 50 – 57 .
   Google Scholar
• Kawatra , R. and Bricker , D. “Design of a Degree-Constrained Minimal Spanning Tree with Unreliable Links and Node Outage Costs.” European Journal of Operational Research 156 ( 2004 ): 73 – 82 .
   Google Scholar
• Knowles , J. and Corne , D. “A New Evolutionary Approach to the Degree-Constrained Minimum Spanning Tree Problem.” IEEE Transactions on Evolutionary Computation 4 , no. 2 ( 2000 ): 125 – 34 .
   Google Scholar
• Krishnamoorthy , M. and Ernst , A. T. “Comparison of Algorithms for the Degree Constrained Minimum Spanning Tree.” Journal of Heuristics 7 ( 2001 ): 587 – 611 .
   Web of Science ®Google Scholar
• Martins , P. and de Souza , M. C. “VNS and Second Order Heuristics for the Min-Degree Constrained Minimum Spanning Tree Problem.” Computers and Operations Research 36 ( 2009 ): 2969 – 82 .
   Google Scholar
• Monma , C. and Suri , S. “Transitions in Geometric Minimum Spanning Trees.” Discrete Computational Geometry 8 ( 1992 ): 265 – 93 .
   Google Scholar
• Narendra , K. S. and Thathachar , M. A. L. Learning Automata: An Introduction . New York : Prentice-Hall , 1989 .
   Google Scholar
• Oncan , T. “Design of Capacitated Minimum Spanning Tree with Uncertain Cost and Demand Parameters.” Information Sciences 177 ( 2007 ): 4354 – 67 .
   Web of Science ®Google Scholar
• Papadimitriou , C. H. and Vazirani , U. V. “On Two Geometric Problems Related to the Travelling Salesman Problem.” Journal of Algorithms 5 , no. 2 ( 1984 ): 231 – 46 .
   Google Scholar
• Parsa , M. , Zhu , Q. , and Garcia-Luna-Aceves , J. J. “An Iterative Algorithm for Delay-Constrained Minimum-Cost Multicasting.” IEEE/ACM Transactions on Networking 6, no. 4 (1998): 461–74.
   Web of Science ®Google Scholar
• Pereira , T. L. , Carrano , E. G. , Takahashi , R. H. C. , Wanner , E. F. , and Neto , O. M. “Continuous-Space Embedding Genetic Algorithm Applied to the Degree Constrained Minimum Spanning Tree Problem.” Paper presented at the IEEE Congress on Evolutionary Computation, 18–21 May 2009, Norway. p. 1391–8 .
   Google Scholar
• Raidl , G. R. “An Efficient Evolutionary Algorithm for the Degree-Constrained Minimum Spanning Tree Problem.” Paper presented at the 2000 Congress on Evolutionary Computation, 6–19 July 2000, La Jolla, CA, USA. p. 104–11 .
   Google Scholar
• Raidl , G. R. and Julstrom , B. A. “A Weighted Coding in a Genetic Algorithm for the Degree-Constrained Minimum Spanning Tree Problem.” Paper presented at the 2000 ACM Symposium on Applied Computing, 19–21 March 2000, Italy. p. 440–5 .
   Google Scholar
• Ribeiro , C. C. and Souza , M. C. “Variable Neighborhood Search for the Degree-Constrained Minimum Spanning Tree Problem.” Discrete Applied Mathematics 118 ( 2002 ): 43 – 54 .
   Web of Science ®Google Scholar
• Salama , H. F. , Reeves , D. S. , and Viniotis , Y. “The Delay-Constrained Minimum Spanning Tree Problem.” Paper presented at the Second IEEE Symposium on Computers and Communications, 1–3 July 1997, Alexandria, Egypt. p. 699–703 .
   Google Scholar
• Soak , S.-M. , Corne , D. , and Ahn , B.-H. “A New Encoding for the Degree Constrained Minimum Spanning Tree Problem.” Lecture Notes in Computer Science 3213 ( 2004 ): 952 – 8 .
   Google Scholar
• Thathachar , M. A. L. and Harita , B. R. “Learning Automata with Changing Number of Actions.” IEEE Transactions on Systems, Man, and Cybernetics 17 ( 1987 ): 1095 – 1100 .
   Web of Science ®Google Scholar
• Volgenant , A. “A Lagrangean Approach to the Degree-Constrained Minimum Spanning Tree Problem.” European Journal of Operational Research 39 ( 1989 ): 325 – 31 .
   Google Scholar
• Zeng , Y. and Wang , Y.-P. “A New Genetic Algorithm with Local Search Method for Degree-Constrained Minimum Spanning Tree Problem.” Paper presented at the Fifth International Conference on Computational Intelligence and Multimedia Applications, 27–30 September 2003, China. p. 218–22 .
   Google Scholar
• Zhou , G. , Gen , M. , and Wu , T. “A New Approach to the Degree-Constrained Minimum Spanning Tree Problem Using Genetic Algorithm.” Paper presented at the IEEE International Conference on Systems, Man, and Cybernetics, 14–17 October 1996, Beijing, China. p. 2683–8 .
   Google Scholar