메뉴 건너뛰기
.. 내서재 .. 알림
소속 기관/학교 인증
인증하면 논문, 학술자료 등을  무료로 열람할 수 있어요.
한국대학교, 누리자동차, 시립도서관 등 나의 기관을 확인해보세요
(국내 대학 90% 이상 구독 중)
로그인 회원가입 고객센터 ENG
주제분류

추천
검색
질문

논문 기본 정보

자료유형
학술저널
저자정보
저널정보
Korean Institute of Information Scientists and Engineers 정보과학회논문지(A) 정보과학회논문지(A) 제23권 제9호
발행연도
1996.9
수록면
957 - 964 (8page)

이용수

표지
📌
연구주제
📖
연구배경
🔬
연구방법
🏆
연구결과
AI에게 요청하기
추천
검색
질문

이 논문의 연구 히스토리 (2)

초록· 키워드

오류제보하기
정점의 수(ㅣVㅣ)가 n이고 간선의 수(ㅣEㅣ)가 m인 연결된 무방향 그래프 G=(V,E)가 주어질 때, E에 속한 임의의 두 간선 e와 g가 같은 간선이거나 같은 단순 사이클에 속하면, e와 g는 같은 이중연결요소에 속하게 되는데, 이때 E를 같은 이중연결요소에 속하는 집합들로 나누는 것을 이중연결요소 문제라 한다. 본 논문에서는 이러한 이중연결요소 문제를 해결하는 최적 임의 병렬 알고리즘을 소개하는데, 이는 먼저 G의 신장 트리를 나타내는 간선리스트가 주어질 때, 이 신장 트리의 오일러 행로를 쉽게 구할 수 있는 적절한 인접리스트를 구한 다음, 이를 이용하여 이중연결요소 문제를 해결하는, Priority CRCW PRAM 상에서 O(logn)시간과 O(n+m)연산으로 수행될 확률이 높은 알고리즘이다.

목차

요약

Abstract

1. 서론

2. 계산 모델 및 기본 알고리즘

3. 오일러 행로

4. 최적 이중연결요소 알고리즘

5. 결론

참고문헌

참고문헌 (0)

참고문헌 신청

함께 읽어보면 좋을 논문

논문 유사도에 따라 DBpia 가 추천하는 논문입니다. 함께 보면 좋을 연관 논문을 확인해보세요!

이 논문의 저자 정보

최근 본 자료

전체보기

댓글(0)

0

UCI(KEPA) : I410-ECN-0101-2009-569-017725992