Earticle

초록

영어

In this paper I propose an algorithm of linear time complexity for NP-complete Maximum Independent Set (MIS) problem. Based on the basic property of the MIS, which forbids mutually adjoining vertices, the proposed algorithm derives the solution by repeatedly selecting vertices in the ascending order of their degree, given that the degree remains constant when vertices v of the minimum degree δ(G) are selected and incidental edges deleted in a graph of n vertices. When applied to 22 graphs, the proposed algorithm could obtain the MIS visually yet effortlessly. The proposed linear MIS algorithm of time complexity O(n) always executes α(G) times, the cardinality of the MIS, and thus could be applied as a general algorithm to the MIS problem.

한국어

본 논문은 지금까지 NP-완전인 난제로 알려진 최대 독립집합(MIS) 문제를 선형시간 복잡도로 해결한 알고리즘 을 제안하였다. 제안된 알고리즘은 “MIS 집합의 모든 정점들은 상호간에 연결되지 않는다”는 기본 성질을 적용하여 n개 의 정점으로 구성된 그래프에서 최소 차수 δ(G) 정점 v를 선택하고 부속 간선을 제거하였을 때 차수가 변하지 않는 정점들을 차수 오름차순으로 계속적으로 선택하는 단순한 방법을 적용하였다. 제안된 알고리즘을 22개 그래프에 적용한 결과, 시각적으로 그래프를 보면서도 MIS를 쉽게 찾을 수 있는 장점을 갖고 있으며, 알고리즘은 항상 MIS 집합의 원소 개수인 α(G) 회를 수행하여 알고리즘 복잡도는 O(n) 으로 선형 알고리즘이다. 결국, 제안된 MIS 알고리즘은 MIS의 최적 해를 도출하는 일반적인 알고리즘으로 적용할 수 있을 것이다.

목차

요약
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