2004년 춘계 학술대회
Current Result Document :
| 한글제목(Korean Title) |
Solid Grid 그래프를 위한 입출력 효율적인 Depth-First Search 알고리즘 |
| 영문제목(English Title) |
External-Memory Depth-First Search Algorithm for Solid Grid Graphs |
| 저자(Author) |
허준호
R. S. Ramakrishna
|
| 원문수록처(Citation) |
VOL 31 NO. 01 PP. 0979 ~ 0981 (2004. 04) |
한글내용
(Korean Abstract) |
여러 과학 및 공학 응용 프로그램에서 다루는 그래프 데이터는 종종 그 크기가 너무 커서 컴퓨터의 주 메모리에 다 들어 갈 수 없는 경우가 많다. 이러한 방대한 크기의 자료를 처리하면서 입출력의 빈도가 자연적으로 커지게 되고 전체 계산에서 주요한 병목 요인으로 작용한다. 본 논문은 solid grid 그래프를 위한 입출력 복잡도(I/O-complexity)가 O(sort(N))인 depth-first search (DFS) 알고리즘을 제안한다. 여기서, N=|V|+|E| 이고 sort(N)=Θ((N/B)logM/B(N/B)) 이다. 이 전까지 알려진 가장 좋은 알고리즘은 적절한 sub-grid 입출력을 바탕으로 한 전통적 DFS 알고리즘으로 그 입출력 복잡도는 O((N/B)B1/2) 이다. |
영문내용
(English Abstract) |
|
| 키워드(Keyword) |
컴퓨터 이론
Solid Grid 그래프
Solid Grid Graph
Depth-First Search 알고리즘
Depth-First Search Algorithm
External-Memory
|
| 파일첨부 |
PDF 다운로드
|
