차수 제약 최소신장트리의 하이브리드 알고리즘 = A Hybrid Algorithm for Degree-Constrained Minimum Spanning Tree

다국어 초록 (Multilingual Abstract)

The degree-constrained minimum spanning tree (d-MST) has been considered nondeterministic polynomial time (NP)-complete because there isn't known polynomial time algorithm. One thus has to resort to an approximate algorithm to obtain an optimal solution to this problem. This paper therefore proposes a polynomial time algorithm wherein Borůvka's and Kruskal's algorithms of unconstrained minimum spanning tree (MST) to obtain the MST, whose degree is then reduced by 1 so as to derive 2-MST of the Hamiltonian path. As a means of swapping degrees, I employ a swap method whereby, from a given MST, maximum-weight edges of a vertex with a degree of are deleted and are swapped with those of while minimizing the incremental degree. When tested on 3 graphs, the proposed algorithm has successfully and handily obtained the optimal solutions. This paper accordingly disproves the NP-completeness of the d-MST.

국문 초록 (Abstract)

무방향 가중 그래프의 차수제약 최소신장트리 (d-MST) 문제는 정확한 해를 구하는 다항시간 알고리즘이 존재하지 않아 NP-완전 문제로 알려져 왔다. 따라서 근사 알고리즘을 적용하여 최적 해를 구하고 있다. 본 논문은 차수를 제약하지 않는 일반적인 최소신장트리를 구하는 Borůvka와 Kruskal 알고리즘으로 MST를 구하고, 차수를 1씩 줄여 가면서 해밀턴 경로인 2-MST 까지 정확히 구하는 다항시간 알고리즘을 제안하였다. 차수를 교환하는 방법은 주어진 MST에서 차수 인 정점의 최대 가중치 간선을 제거하고 가중치를 최소로 증가시키면서 가 되는 간선으로 교환하는 방법을 적용하였다. 제안된 알고리즘을 3개의 그래프에 적용한 결과 모두 정확히 2-MST까지 쉽게 최적 해를 구하는데 성공하였다. 따라서 d-MST는 더 이상 NP-완전 문제가 아니며, P-문제임을 보였다.

참고문헌 (Reference)

1 이용진, "WSN의 최소비용 신장트리 문제와 휴리스틱 알고리즘" 한국정보기술학회 7 (7): 275-282, 2009

2 R. C. Prim, "Shortest Connection Networks and Some Generalisations" 36 (36): 1389-1401, 1957

3 J. Nešetřil, "Otakar Borůvka on Minimum Spanning Tree Problem (Translation of the both 1926 Papers, Comments, History)" 233 (233): 3-36, 2001

4 J. B. Kruskal, "On the Shortest Spanning Subtree and The Traveling Salesman Problem" 7 (7): 48-50, 1956

5 O. Borůvka, "O Jistem Problemu Minimalnim" Ⅲ (Ⅲ): 37-58, 1926

6 "Minimum Spanning Tree"

7 M. Gen, "Evolutionary Algorithms and Optimization:Theory and Its Application" Software Computing Lab., Waseda University, IPS 2004

8 M. Savelsbergh, "Edge-Exchanges in the Degree-Constrained Minimum Spanning Tree Problem" 12 (12): 341-348, 1985

9 "Degree-constrained Spanning Tree"

10 C. Peiper, "CS 400 - Data Structures for Non CS-Majors"

11 G. R. Raidl, "An Efficient Evolutionary Algorithm for the Degree-Constrained Minimum Spanning Tree Problem" 1 : 104-111, 2000

12 T. N. Bui, "An Ant-based Algorithm for Finding Degree-Constrained Minimum Spanning Tree" 11-18, 2006

13 M. Behle, "A Primal Branch-and-Cut Algorithm for the Degree-Constrained Minimum Spanning Tree Problem" 4525 : 379-392, 2007

14 W. Guo, "A PSO-Optimized Minimum Spanning Tree-based Topology Control Scheme for Wireless Sensor Networks" 2013 : 1-14, 2013

15 G. Zhou, "A Note on Genetic Algorithms for Degree-Constrained Spanning Tree Problems" 30 (30): 91-95, 1997

16 J. Knowles, "A New Evolutionary Approach to the Degree Constrained Minimum Spanning Tree Problem" 4 (4): 125-134, 2000

17 G. Zhou, "A New Approach to the Degree-Constrained Minimum Spanning Tree Problem Using Genetic Algorithms" 3 (3): 156-165, 1997

18 A. Ning, "A New Algorithm for Degree-Constrained Minimum Spanning Tree Based on the Reduction Technique" 18 (18): 495-499, 2008

19 X. Duan, "A Hybrid Algorithm Based on Particle Swarm Optimization" 1 (1): 275-282, 2005