지원사업
학술연구/단체지원/교육 등 연구자 활동을 지속하도록 DBpia가 지원하고 있어요.
커뮤니티
연구자들이 자신의 연구와 전문성을 널리 알리고, 새로운 협력의 기회를 만들 수 있는 네트워킹 공간이에요.
논문 기본 정보
- 자료유형
- 학술저널
- 저자정보
- 발행연도
- 2018.11
- 수록면
- 1,538 - 1,543 (6page)
이용수
초록· 키워드
오류제보하기
원 상에 n개의 점들의 쌍(a, b) 이 존재할 때, 두 점 a와 b를 연결하는 직선 선분을 코드라고 한다. 이러한 n개의 코드들은 새로운 그래프 G를 정의한다. 각 코드는 G의 한 정점을 정의하고 두 코드가 교차하는 경우에 대응되는 정점들 간에 간선을 연결한다. 이렇게 만들어진 그래프 G를 원 그래프라고 부른다. 본 논문에서는 원 그래프에서 연결요소를 찾는 문제를 다룬다. 연결 요소란 그래프 G의 부분 그래프 H로서 H안의 임의의 두 정점 간에 경로가 존재한다는 조건을 만족하는 최대 부분 그래프이다. 그래프 G가 인접 행렬로 주어지는 경우, 연결 요소를 찾는 문제는 깊이 우선 탐색 또는 너비 우선 탐색을 통해서 해결할 수 있다. 하지만 원 그래프의 경우에 코드들을 정의하는 n개의 점들의 쌍 정보만 입력으로 주어질 때, 인접 행렬을 구하는데 Ω(n²)시간이 소요됨을 알 수 있다. 본 논문에서는 인접 행렬을 만들지 않고 원 그래프의 연결 요소를 O(nlog²n) 시간에 찾는 알고리즘을 고안한다.
목차
요약
ABSTRACT
Ⅰ. 서론
Ⅱ. 관련 연구
Ⅲ. 문제 정의
Ⅳ. 알고리즘
Ⅴ. 알고리즘 시간분석
Ⅵ. 결론
REFERENCES
참고문헌 (12)
참고문헌 신청
[단행본] - M. C. Golumbic / 1980 / Algorithmic Graph Theory and Perfect Graphs / Academic Press
[학술지(정기간행물)] - X. Yang / 2008 / Largest connected component of a star graph with faulty vertices / International Journal of Computer Mathematics 85 (12) : 1771 ~ 1778
[학술지(정기간행물)] - R. Jaberi / 2016 / On computing the 2-vertex-connected components of directed graps / Discrete Applied Mathematics 204 : 164 ~ 172
[학술대회논문] - M. Henzinger / 2015 / Finding 2-edge and 2-vertex strongly connected components in quadratic time / Proceedings of the 42h International Colloquium on Automata, Language, and Programming : 713 ~ 724
[학술지(정기간행물)] - X. Allamigeon / 2014 / On the complexity of strongly connected components in directed hypergraph / Algorithmica 69 (2) : 335 ~ 369
[학술지(정기간행물)] - X. Yang / 2008 / Largest connected component of a star graph with faulty vertices / International Journal of Computer Mathematics 85 (12) : 1771 ~ 1778
[학술지(정기간행물)] - R. Jaberi / 2016 / On computing the 2-vertex-connected components of directed graps / Discrete Applied Mathematics 204 : 164 ~ 172
[학술대회논문] - M. Henzinger / 2015 / Finding 2-edge and 2-vertex strongly connected components in quadratic time / Proceedings of the 42h International Colloquium on Automata, Language, and Programming : 713 ~ 724
[학술지(정기간행물)] - X. Allamigeon / 2014 / On the complexity of strongly connected components in directed hypergraph / Algorithmica 69 (2) : 335 ~ 369
함께 읽어보면 좋을 논문
논문 유사도에 따라 DBpia 가 추천하는 논문입니다. 함께 보면 좋을 연관 논문을 확인해보세요!
-
사용자, 아이템 그래프를 활용한 효율적 행렬채움 알고리즘
대한전자공학회 학술대회
2020 .08
-
그래프의 정점 연결성에 대한 최소 범위 할당
한국정보통신학회논문지
2017 .11
-
요약 그래프 상에서 효과적인 그래프 압축 기법
한국정보과학회 학술발표논문집
2016 .06
-
외부 지식 그래프 결합을 위한 그래프 트랜스포머 알고리즘
한국정보과학회 학술발표논문집
2023 .06
-
소셜그래프를 활용한 효율적 행렬채움 알고리즘
한국정보통신학회논문지
2023 .11
-
동적 그래프에서 효율적인 그래프 요약 기법
한국정보과학회 학술발표논문집
2015 .12
-
최신 그래프 처리 시스템에서의 약한 연결 요소 처리 성능 평가
한국정보과학회 학술발표논문집
2018 .06
-
사상 행렬을 이용한 효율적인 그래프 편집 거리 학습 기법
한국정보과학회 학술발표논문집
2024 .06
-
An Embedding Technique for Weighted Graphs using LSTM Autoencoders
Journal of KIISE
2021 .01
-
Efficient Shortest Path Techniques on a Summarized Graph based on the Relationships
Journal of KIISE
2017 .07
-
확장 그래프에서 그래프 신경망을 사용한 다 기준 추천
한국통신학회 학술대회논문집
2023 .02
-
그래프 중심성들을 이용한 그래프 유사도 측정
한국컴퓨터정보학회논문지
2018 .12
-
GPU에서 CUDA를 이용한 그래프 유사도 측정을 위한 병렬 알고리즘
정보과학회 컴퓨팅의 실제 논문지
2017 .03
-
소스코드의 그래프 변환을 통한 시각화와 그래프 도구 활용에 대한 연구
한국소프트웨어감정평가학회논문지
2024 .03
-
영상 검색에서 그래프 구조를 이용한 스켈레톤 데이터 그래프 모델링 기법
한국정보과학회 학술발표논문집
2020 .12
-
그래프 오더링을 활용한 그래프 병렬 처리의 성능 향상
한국정보과학회 학술발표논문집
2017 .12
-
One-step Graph-based Clustering via Learning Robust and Structured Graph from Corrupted Single-view
전자공학회논문지
2022 .05
-
GPU를 이용한 경로 기반 하이브리드 그래프 처리 기법
정보과학회 컴퓨팅의 실제 논문지
2024 .11
-
공간 운동 기구의 형태 합성을 위한 그래프 열거 방법 개발
한국자동차공학회 추계학술대회 및 전시회
2018 .11
-
주어진 무방향성 연결 그래프로부터 방향성이 있는 수형도를 생성하는 알고리즘
제어로봇시스템학회 국내학술대회 논문집
2018 .05
이 논문의 저자 정보
이 논문과 함께 이용한 논문
최근 본 자료
댓글(0)
0