:: The Journal of the Institute of Internet, Broadcasting and Communication ::, Vol.25 No.1 | (2025) pp.89~96
최소 가중치 연결 지배집합 문제의 최소신장트리-기반 중추 집합 알고리즘
Abstract
본 논문은 NP-완전 문제로 분류된 최소 가중치 연결 지배집합 문제(MWCDSP)에 대해 다항시간의 정확한 해를 찾는 알고리즘을 제안하였다. MWCDSP의 최적 해를 직접적으로 찾는 규칙을 발견하는 것은 불가능에 가깝다. MWCDSP의 전제조건은 최소 가중치 합과 연결된 최소 노드 수를 충족시켜야만 한다. 본 논문은 먼저 최소 가중치 합을 가진 개 노드를 연결하는 MST를 구하였다. 다음으로 연결된 최소 노드 수 조건을 충족시키기 위해 MST의 내부 노드 들 중에서 차수가 2 이상인 단 노드들을 지배하는 노드를 단 노드로 변환시켜 연결된 노드 수를 줄였다. 제안된 알고리 즘을 14개의 다양한 유형의 망에 대해 적용한 결과 모든 망에서 최적 해를 찾을 수 있음을 보였다.
This paper proposes an algorithm to find the exact solution of polynomial time for the minimum weighted connected dominating set problem(MWCDSP) classified as NP-complete problem. It is almost impossible to find a rule that directly finds the optimal solution of MWCDSP. The prerequisite for MWCDSP must meet the minimum sum of weights and the minimum number of connected nodes with it. This paper first obtains an MST that connecting n nodes with a minimum weighted sum. Next, in order to meet the condition of the minimum number of connected nodes, the nodes that dominating the terminal nodes with a degree of 2 or higher among the internal nodes of the MST were converted to the terminal nodes to reduce the number of connected nodes. The application of the proposed algorithm to 14 different types of networks shows that the optimal solution can be found in all networks.
Minimum weighted connected dominating set(MWCDS),Minimum spanning tree(MST),Minimum Backbone set(MBS),Internal node,Terminal node
