Earticle

초록

영어

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.

한국어

본 논문은 NP-완전 문제로 분류된 최소 가중치 연결 지배집합 문제(MWCDSP)에 대해 다항시간의 정확한 해를 찾는 알고리즘을 제안하였다. MWCDSP의 최적 해를 직접적으로 찾는 규칙을 발견하는 것은 불가능에 가깝다. MWCDSP의 전제조건은 최소 가중치 합과 연결된 최소 노드 수를 충족시켜야만 한다. 본 논문은 먼저 최소 가중치 합을 가진 개 노드를 연결하는 MST를 구하였다. 다음으로 연결된 최소 노드 수 조건을 충족시키기 위해 MST의 내부 노드 들 중에서 차수가 2 이상인 단 노드들을 지배하는 노드를 단 노드로 변환시켜 연결된 노드 수를 줄였다. 제안된 알고리 즘을 14개의 다양한 유형의 망에 대해 적용한 결과 모든 망에서 최적 해를 찾을 수 있음을 보였다.

목차

요약
Abstract
Ⅰ. 서론
Ⅱ. 문제 정의, 관련연구와 문제점
Ⅲ. MST 기반 중추 집합 알고리즘
Ⅳ. 실험 및 결과 분석
Ⅴ. 결론
References

키워드

저자

• 이상운 [ Sang-Un Lee | 정회원, 강릉원주대학교 과학기술대학 멀티미디어공학과 교수 ] Corresponding Author

참고문헌

발행기관

간행물

표지보기 관심저널 등록

• 간행물명

  한국인터넷방송통신학회 논문지 [The Journal of the Institute of Internet, Broadcasting and Communication]

• 간기

  격월간

• pISSN

  2289-0238

• eISSN

  2289-0246

• 수록기간

  2001~2025

• 십진분류

  KDC 326 DDC 380