본문 바로가기
HOME> 논문 > 논문 검색상세

논문 상세정보

O(log n)의 병렬 시간이 소요되는 Solid Grid 그래프를 위한 Depth-First Search 알고리즘
(An O(log n) Parallel-Time Depth-First Search Algorithm for Solid Grid Graphs

허준호 ;    (광주과학기술원 정보통신공학과   );
  • 초록

    본 논문은 평면 그래프를 위한 병렬 depth-first search (DFS) 알고리즘 [SIAM J. Comput., 19 (1990) 678-704]을 비 평면일 (non-planar) 수 있는 grid 그래프의 한 종류인 solid grid 그래프에 대해서도 수행 가능하도록 확장된 알고리즘을 제안한다. 제안 알고리즘은 Priority PRAM 모델에서 $O(n/sqrt{log\;n})$ 개의 프로세서로 수행했을 때 O(log n)의 병렬 시간이 소요된다. 우리의 지식으로, 이는 비 평면 그래프를 위한 첫 번째 결정적 NC (deterministic NC) 알고리즘이다.


    We extend a parallel depth-first search (DFS) algorithm for planar graphs to deal with (non-planar) solid grid graphs, a subclass of non-planar grid graphs. The proposed algorithm takes time O(log n) with $O(n/sqrt{log\;n})$ processors in Priority PRAM model. In our knowledge, this is the first deterministic NC algorithm for a non-planar graph class.


  • 주제어

    병렬 알고리즘 .   그래프 알고리즘 .   (비)평면 그래프.  

  • 참고문헌 (15)

    1. V. Ramachandran, Parallel open ear decomposition with applications to graph biconnectivity, and triconnectivity, in Synthesis of Parallel Algorithms, J. Reif, ed., Morgan-Kaufmann, pp. 275-340, 1993 
    2. R. Tarjan, Depth-first search and linear graph algorithms, SIAM J. Comput., Vol.1, No.2, pp.146-160, 1972 
    3. E. Charniak and D. McDermott, Introduction to artificial intelligence, Addison-Wesley, 1985 
    4. E. Reghgati and D. Corneil, Parallel computations in graph theory, SIAM J. Comput., Vol.7, No.3, pp.230-237, 1978 
    5. J. H. Reif, Depth-first searches inherently sequential, Inform. Process. Lett., Vol.20, No.5, pp.229-234, 1985 
    6. A. Aggarwal and R. J. Anderson, A random NC algorithm for depth-first search, Combinatorica, Vol.8, No.1, pp.1-12, 1988 
    7. A. Aggarwal, Richard J. Anderson, and Ming-Yang Kao, Parallel depth-first search in general directed graphs, SIAM J. Comput., Vol.19, No.2, pp.397-409, 1990 
    8. Jun-Ho Her and R. S. Ramakrishna, External-memory depth-first search algorithm for solid grid graphs, Information Processing Letters, Vol.93, No.4, pp.177 -183, 2005 
    9. J. R. Smith, Parallel algorithms for depth-first searches I. Planar graphs, SIAM J. Comput., Vol.15, No.3, pp.814-830, 1986 
    10. A. V. Goldberg, S. A. Plotkin, and G. E. Shannon, Parallel symmetry-breaking in sparse graphs, SIAM J. Discrete Math., Vol.1, No.1, pp.434-446, 1988 
    11. G. E. Shannon, A linear-processor algorithm for depth-first search in planar graphs, Inform. Process. Lett., Vol.29, No.3, pp.119-123, 1988 
    12. T. Hagerup, Planar depth-first search in O(log n) parallel time, SIAM J. Comput., Vol.l9, No.4, pp.678-704, 1990 
    13. Ming-Yang Kao, Shang-Hua Teng, and K. Toyama, An optimal parallel algorithm for planar cycle separators, Proc. of the 3rd Int. Workshop on Algorithms and Data Structures, pp.407-420, 1993 
    14. Greg N. Frederickson, Fast algorithms for shortest paths in planar graphs, with applications, SIAM J. Comput, Vol.16, No.6, pp.1004-1022, 1987 
    15. L. Arge, L. Toma, and J. S. Vitter, 'I/O-Efficient Algorithms for Problems on Grid-based Terrains,' Journal of Experimental Algorithms, Vol.6, No.1, pp.1-19, 2001 

 저자의 다른 논문

  • 허준호 (0)

 활용도 분석

  • 상세보기

    amChart 영역
  • 원문보기

    amChart 영역

원문보기

무료다운로드
  • NDSL :
유료다운로드

유료 다운로드의 경우 해당 사이트의 정책에 따라 신규 회원가입, 로그인, 유료 구매 등이 필요할 수 있습니다. 해당 사이트에서 발생하는 귀하의 모든 정보활동은 NDSL의 서비스 정책과 무관합니다.

원문복사신청을 하시면, 일부 해외 인쇄학술지의 경우 외국학술지지원센터(FRIC)에서
무료 원문복사 서비스를 제공합니다.

NDSL에서는 해당 원문을 복사서비스하고 있습니다. 위의 원문복사신청 또는 장바구니 담기를 통하여 원문복사서비스 이용이 가능합니다.

이 논문과 함께 출판된 논문 + 더보기