@article{ART001992786},
author={Sang-Un, Lee},
title={A Degree-Constrained Minimum Spanning Tree Algorithm Using k-opt},
journal={Journal of The Korea Society of Computer and Information},
issn={1598-849X},
year={2015},
volume={20},
number={5},
pages={31-39}
TY - JOUR
AU - Sang-Un, Lee
TI - A Degree-Constrained Minimum Spanning Tree Algorithm Using k-opt
JO - Journal of The Korea Society of Computer and Information
PY - 2015
VL - 20
IS - 5
PB - The Korean Society Of Computer And Information
SP - 31
EP - 39
SN - 1598-849X
AB - The degree-constrained minimum spanning tree (d-MST) problem is considered NP-complete for no exact solution-yielding polynomial algorithm has been proposed to. One thus has to resort to an heuristic approximate algorithm to obtain an optimal solution to this problem. This paper therefore presents a polynomial time algorithm which obtains an intial solution to the d-MST with the help of Kruskal's algorithm and performs k-opt on the initial solution obtained so as to derive the final optimal solution.
When tested on 4 graphs, the algorithm has successfully obtained the optimal solutions.
KW - Minimumspanning tree;Degree constrained;Hamiltonian path;k-opt edge swap
DO -
UR -
ER -
Sang-Un, Lee. (2015). A Degree-Constrained Minimum Spanning Tree Algorithm Using k-opt. Journal of The Korea Society of Computer and Information, 20(5), 31-39.
Sang-Un, Lee. 2015, "A Degree-Constrained Minimum Spanning Tree Algorithm Using k-opt", Journal of The Korea Society of Computer and Information, vol.20, no.5 pp.31-39.
Sang-Un, Lee "A Degree-Constrained Minimum Spanning Tree Algorithm Using k-opt" Journal of The Korea Society of Computer and Information 20.5 pp.31-39 (2015) : 31.
Sang-Un, Lee. A Degree-Constrained Minimum Spanning Tree Algorithm Using k-opt. 2015; 20(5), 31-39.
Sang-Un, Lee. "A Degree-Constrained Minimum Spanning Tree Algorithm Using k-opt" Journal of The Korea Society of Computer and Information 20, no.5 (2015) : 31-39.
Sang-Un, Lee. A Degree-Constrained Minimum Spanning Tree Algorithm Using k-opt. Journal of The Korea Society of Computer and Information, 20(5), 31-39.
Sang-Un, Lee. A Degree-Constrained Minimum Spanning Tree Algorithm Using k-opt. Journal of The Korea Society of Computer and Information. 2015; 20(5) 31-39.
Sang-Un, Lee. A Degree-Constrained Minimum Spanning Tree Algorithm Using k-opt. 2015; 20(5), 31-39.
Sang-Un, Lee. "A Degree-Constrained Minimum Spanning Tree Algorithm Using k-opt" Journal of The Korea Society of Computer and Information 20, no.5 (2015) : 31-39.
