Earticle

초록

영어

This paper proposes an algorithm that can obtain a solution with linear time for a set cover problem(SCP) in which there is no polynomial time algorithm as an NP-complete problem so far. Until now, only heuristic greed algorithms are known to select sets that can be covered to the maximum. On the other hand, the proposed algorithm is a competitive algorithm that applies an inclusion-exclusion principle rule to N nodes up to 2nd or 3rd in the maximum number of elements to obtain a set covering all k nodes, and selects the minimum cover set among them. The proposed algorithm compensated for the disadvantage that the greedy algorithm does not obtain the optimal solution. As a result of applying the proposed algorithm to various application cases, an optimal solution was obtained with a polynomial time of O(kn2).

한국어

본 논문은 지금까지 NP-완전 문제로 다항시간 알고리즘이 존재하지 않는 집합피복 문제에 대해 선형시간으로 해를 구할 수 있는 알고리즘을 제안하였다. 지금까지는 최대로 피복할 수 있는 집합을 선택하는 휴이스틱 탐욕 알고리즘 만이 알려져 있다. 반면에 제안된 알고리즘은 최대 원소 수 2순위 또는 3순위까지의 노드들 k개를 대상으로 포함-배제 원리 규칙을 적용하여 N개의 노드 모두를 피복하는 피복집합을 구하고, 이들 중 최소 피복집합을 선택하는 경쟁 알고리 즘이다. 제안된 알고리즘은 욕심쟁이 알고리즘이 최적 해를 얻지 못하는 단점을 보완하였다. 제안된 알고리즘을 다양한 응용 사례들에 적용한 결과 O(kn2)의 다항시간으로 최적 해를 얻었다.

목차

요약
Abstract
Ⅰ. 서론
Ⅱ. 관련연구와 문제점
Ⅲ. 경쟁 알고리즘
Ⅳ. 실험 및 결과 분석
Ⅴ. 결론 및 향후 연구과제
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