지원사업
학술연구/단체지원/교육 등 연구자 활동을 지속하도록 DBpia가 지원하고 있어요.
커뮤니티
연구자들이 자신의 연구와 전문성을 널리 알리고, 새로운 협력의 기회를 만들 수 있는 네트워킹 공간이에요.
논문 기본 정보
- 자료유형
- 학술저널
- 저자정보
- 발행연도
- 2016.2
- 수록면
- 415 - 420 (6page)
이용수
초록· 키워드
오류제보하기
선분 그래프(interval graph) G=(V, E)는 직선 상의 선분들을 나타내는 정점 집합 V와 간선 (i, j)∈E는 선분 i 와 j가 교차함을 나타내는 간선들의 집합 E로 이루어진다. 본 논문에서는 그래프의 여러 특성 중에서 정점 연결성(vertex connectivity)에 주목한다. 특별히 선분들이 겹쳐지는 모습으로 선분 그래프의 정점 연결성을 나타낸다. 또한 선분 그래프에서 정점이나 간선이 추가 되거나 삭제되는 완전 동적 (fully dynamic) 환경에서 정점 연결성을 계산하는 효율적인 알고리즘을 제안할 것이다. 특별한 형태의 선분 트리(interval tree)를 사용하여 새로운 선분이 추가되거나 삭제되는 상황 하에서 정점 연결성을 계산하고 트리를 유지하는데 O(logn) 시간이 소요됨을 보일 것이다.
목차
요약
ABSTRACT
Ⅰ. 서론
Ⅱ. 관련 연구
Ⅲ. 알고리즘 및 분석
Ⅳ. 결론
REFERENCES
참고문헌 (12)
참고문헌 신청
M. C. Golumbic, Algorithmic Graph Theory and Perfect Graphs, New York, NY: Academic Press, 1980.
J. M. Keil, “Finding hamiltonian circuits in interval graphs,” Information Processing Letters, vol. 20, pp. 201-206, May 1985.
G. Ramalingam and C. Pandu Rangan, “A unified approach to domination problems on interval graphs,” Information Processing Letters, vol. 27, pp. 271-274, April 1988.
A. Srinivasa Rao and C. Pandu Rangan, “Linear algorithm for domatic number problem on interval graphs,” Information Processing Letters, vol. 33, pp. 29-33, Oct. 1989.
H. Broersma, Jiri Fiala, P. A. Golovach, T. Kaiser, D. Paulusma, and A. Proskurowski, “Linear-time algorithms for scattering number and hamilton-connectivity of interval graphs,” Journal of Graph Theory, vol. 79, pp. 282-299, Aug. 2015.
J. M. Keil, “Finding hamiltonian circuits in interval graphs,” Information Processing Letters, vol. 20, pp. 201-206, May 1985.
G. Ramalingam and C. Pandu Rangan, “A unified approach to domination problems on interval graphs,” Information Processing Letters, vol. 27, pp. 271-274, April 1988.
A. Srinivasa Rao and C. Pandu Rangan, “Linear algorithm for domatic number problem on interval graphs,” Information Processing Letters, vol. 33, pp. 29-33, Oct. 1989.
H. Broersma, Jiri Fiala, P. A. Golovach, T. Kaiser, D. Paulusma, and A. Proskurowski, “Linear-time algorithms for scattering number and hamilton-connectivity of interval graphs,” Journal of Graph Theory, vol. 79, pp. 282-299, Aug. 2015.
함께 읽어보면 좋을 논문
논문 유사도에 따라 DBpia 가 추천하는 논문입니다. 함께 보면 좋을 연관 논문을 확인해보세요!
-
그래프의 정점 연결성에 대한 최소 범위 할당
한국정보통신학회논문지
2017 .11
-
선분 그래프에서의 두 번째 모든 쌍 최단 경로 알고리즘에 관한 연구
한국정보과학회 학술발표논문집
2015 .12
-
그래프 중심성들을 이용한 그래프 유사도 측정
한국컴퓨터정보학회논문지
2018 .12
-
동적 그래프에서 효율적인 그래프 요약 기법
한국정보과학회 학술발표논문집
2015 .12
-
중심성이 높은 정점의 변화에 따른 네트워크 특성 분석
한국컴퓨터정보학회논문지
2017 .03
-
The Classification of random graph models using graph centralities
한국컴퓨터정보학회논문지
2019 .07
-
GPGPU 를 이용한 로컬 노드 연결성 계산 최적화 연구
제어로봇시스템학회 논문지
2023 .10
-
A Graph Embedding Technique for Weighted Graphs Based on LSTM Autoencoders
JIPS(Journal of Information Processing Systems)
2020 .01
-
그래프 정보를 이용한 그래프 구조 간략화 알고리즘
제어로봇시스템학회 국내학술대회 논문집
2016 .03
-
User-state Prediction using Brain Connectivity
제어로봇시스템학회 국제학술대회 논문집
2019 .10
-
A Graph2Tree Model for Solving Korean Math Word Problems
Journal of KIISE
2022 .10
-
그래프데이터베이스 기반 통신망 운영관리 방안
한국정보통신학회 종합학술대회 논문집
2022 .05
-
최신 그래프 처리 시스템에서의 동적 그래프를 위한 업데이트 수행 방식에 대한 조사
한국정보과학회 학술발표논문집
2018 .06
-
요약 그래프 상에서 효과적인 그래프 압축 기법
한국정보과학회 학술발표논문집
2016 .06
-
서비스 로봇을 위한 그래프 구조 맵에서의 작업 계획
대한기계학회 춘추학술대회
2019 .11
-
외부 지식 그래프 결합을 위한 그래프 트랜스포머 알고리즘
한국정보과학회 학술발표논문집
2023 .06
-
An Embedding Technique for Weighted Graphs using LSTM Autoencoders
Journal of KIISE
2021 .01
-
Massive Connectivity 제공 기술
전자공학회지
2016 .04
-
동적 환경 소셜 네트워크 그래프에서 다중 제약 조건 그래프 패턴 매칭
한국정보과학회 학술발표논문집
2015 .12
-
GPU에서 CUDA를 이용한 그래프 유사도 측정을 위한 병렬 알고리즘
정보과학회 컴퓨팅의 실제 논문지
2017 .03
이 논문의 저자 정보
이 논문과 함께 이용한 논문
최근 본 자료
댓글(0)
0
UCI(KEPA) : I410-ECN-0101-2016-559-002649084