지원사업
학술연구/단체지원/교육 등 연구자 활동을 지속하도록 DBpia가 지원하고 있어요.
커뮤니티
연구자들이 자신의 연구와 전문성을 널리 알리고, 새로운 협력의 기회를 만들 수 있는 네트워킹 공간이에요.
논문 기본 정보
- 자료유형
- 학술저널
- 저자정보
- 발행연도
- 2017.11
- 수록면
- 2,103 - 2,108 (6page)
이용수
초록· 키워드
오류제보하기
m차원 평면 R<SUP>m</SUP>상에 n개의 점들 p<SUB>i</SUB>가 주어질 때, 범위 r에 대해서, 점 p<SUB>i</SUB>로부터 거리 r이내 점들의 집합 T<SUB>i</SUB>를 생각한다. m=1일 때, T<SUB>i</SUB>는 직선상의 구간이고, m=2일 때, T<SUB>i</SUB>는 평면상의 원에 해당된다. 집합 T<SUB>i</SUB>들을 정점에 대응하고, 두 집합이 교차하는 경우에 대응하는 두 정점 사이에 간선를 연결하면 교차 그래프 G를 얻을 수 있다. m=1일 때, G는 진구간 그래프(proper interval graph), m=2 일 때, G는 단위 원판 그래프(unit disk graph)라고 부른다. 본 논문에서는 범위 r이 변화하면 바뀌는 교차 그래프 G(r)에 관심이 있다. 특별히 G(r)가 연결 그래프가 되는 최소 r을 찾는 문제를 다룰 것이다. 이 문제에 대해서 진구간 그래프 G(r)에 대해서 O(n)시간 알고리즘, 단위 원판 그래프 G(r) 에 대해서 (n² log n)시간 알고리즘을 제안한다. 직선상의 점들이 추가 되거나 삭제되는 동적 환경 하에서 위 문제를 O(log n)시간에 해결하는 알고리즘도 제안한다.
목차
요약
ABSTRACT
Ⅰ. 서론
Ⅱ. 관련 연구
Ⅲ. 1차원 문제
Ⅳ. 2차원 문제
Ⅴ. 동적 환경 문제
Ⅵ. 결론
REFERENCES
참고문헌 (13)
참고문헌 신청
M. C. Golumbic, Algorithmic Graph Theory and Perfect Graphs, New York, NY: Academic Press, 1980.
Terry. A. McKee and F. R. McMorris, Topics in Intersection Graph Theory, Philadelphia, PA: SIAM, 1999.
M. Pal, “Intersection graphs: an introduction,” Annals of Pure and Applied Mathematics, vol. 4, no. 1, pp. 43-91, Oct. 2013.
S. Even and R. E. Tarjan, “Network flow and testing graph connectivity,” SIAM Journal on Computing, vol. 4, no. 4, pp. 507-518, Oct. 1975.
P. K. Ghosh and M. Pal, “An Efficient algorithm to solve connectivity problem on trapezoid graphs,” Journal of Applied Mathematics and Computing, vol. 24, no. 2, pp. 141-154, May 2007.
Terry. A. McKee and F. R. McMorris, Topics in Intersection Graph Theory, Philadelphia, PA: SIAM, 1999.
M. Pal, “Intersection graphs: an introduction,” Annals of Pure and Applied Mathematics, vol. 4, no. 1, pp. 43-91, Oct. 2013.
S. Even and R. E. Tarjan, “Network flow and testing graph connectivity,” SIAM Journal on Computing, vol. 4, no. 4, pp. 507-518, Oct. 1975.
P. K. Ghosh and M. Pal, “An Efficient algorithm to solve connectivity problem on trapezoid graphs,” Journal of Applied Mathematics and Computing, vol. 24, no. 2, pp. 141-154, May 2007.
함께 읽어보면 좋을 논문
논문 유사도에 따라 DBpia 가 추천하는 논문입니다. 함께 보면 좋을 연관 논문을 확인해보세요!
-
그래프 중심성들을 이용한 그래프 유사도 측정
한국컴퓨터정보학회논문지
2018 .12
-
중심성이 높은 정점의 변화에 따른 네트워크 특성 분석
한국컴퓨터정보학회논문지
2017 .03
-
The Classification of random graph models using graph centralities
한국컴퓨터정보학회논문지
2019 .07
-
그래프 정보를 이용한 그래프 구조 간략화 알고리즘
제어로봇시스템학회 국내학술대회 논문집
2016 .03
-
A Graph Embedding Technique for Weighted Graphs Based on LSTM Autoencoders
JIPS(Journal of Information Processing Systems)
2020 .01
-
그래프데이터베이스 기반 통신망 운영관리 방안
한국정보통신학회 종합학술대회 논문집
2022 .05
-
동적 그래프에서 효율적인 그래프 요약 기법
한국정보과학회 학술발표논문집
2015 .12
-
요약 그래프 상에서 효과적인 그래프 압축 기법
한국정보과학회 학술발표논문집
2016 .06
-
동적 대용량 그래프에서 효율적인 디스크 기반 그래프 압축 기법
한국정보과학회 학술발표논문집
2015 .12
-
An Embedding Technique for Weighted Graphs using LSTM Autoencoders
Journal of KIISE
2021 .01
-
특허 지식그래프를 위한 지식 그래프 임베딩 모델 분석 연구
Proceedings of KIIT Conference
2020 .10
-
외부 지식 그래프 결합을 위한 그래프 트랜스포머 알고리즘
한국정보과학회 학술발표논문집
2023 .06
-
그래프 정점과 이웃 점의 특징을 상대적으로 집계한 3차원 어텐션 매커니즘 기반의 그래프 합성곱 신경망
한국정보통신학회 종합학술대회 논문집
2023 .10
-
확장 그래프에서 그래프 신경망을 사용한 다 기준 추천
한국통신학회 학술대회논문집
2023 .02
-
최신 그래프 처리 시스템에서의 동적 그래프를 위한 업데이트 수행 방식에 대한 조사
한국정보과학회 학술발표논문집
2018 .06
-
디스크 기반 그래프 엔진의 입출력 성능 향상을 위한 그래프 오더링
정보과학회 컴퓨팅의 실제 논문지
2018 .01
-
GPU에서 CUDA를 이용한 그래프 유사도 측정을 위한 병렬 알고리즘
정보과학회 컴퓨팅의 실제 논문지
2017 .03
-
Unified Graph Clustering via Learning Robust and Structured Graph
대한전자공학회 학술대회
2019 .06
-
GPU를 이용한 경로 기반 하이브리드 그래프 처리 기법
정보과학회 컴퓨팅의 실제 논문지
2024 .11
-
그래프 오더링을 활용한 그래프 병렬 처리의 성능 향상
한국정보과학회 학술발표논문집
2017 .12
이 논문의 저자 정보
이 논문과 함께 이용한 논문
최근 본 자료
댓글(0)
0
UCI(KEPA) : I410-ECN-0101-2018-004-001532786