2012년 컴퓨터종합학술대회
Current Result Document :
| 한글제목(Korean Title) |
Pregel을 이용한 독립집합 문제의 병렬 분산 알고리즘 |
| 영문제목(English Title) |
A Parallel Distributed Algorithm of the Independent Set Problem using Pregel |
| 저자(Author) |
신은옥
이성민
정연돈
Eunok Shin
Sungmin Yi
Yon Dohn Chung
|
| 원문수록처(Citation) |
VOL 39 NO. 1(C) PP. 0104 ~ 0106 (2012. 06) |
한글내용
(Korean Abstract) |
다양한 그래프 문제들은 대부분 NP-완전 문제로, 그 중 하나인 독립집합을 구하는 문제 또한 최적의 알고리즘이 존재하지 않는다. 따라서 규모가 큰 대용량 그래프 데이터로 독립집합 문제를 처리하기 위해서는 많은 시간과 비용이 소요된다. 이를 효율적으로 해결하기 위해 분산 환경에서 그래프 처리에 적합한 모델인 Pregel을 이용하여 독립집합 문제를 푼다. 이를 위해 정점 사이의 메시지 전달에 따른 정점 상태 변환 방법을 이용하여 분산 병렬 환경에 알맞은 알고리즘을 제안한다.
|
영문내용
(English Abstract) |
|
| 키워드(Keyword) |
|
| 파일첨부 |
PDF 다운로드
|
