선분 그래프의 정점 연결성에 대한 완전 동적 알고리즘

김재훈; Jae-hoon Kim

연구문헌

국내 논문지

홈 > 연구문헌 > 국내 논문지 > 한국정보통신학회 논문지 (Journal of the Korea Institute of Information and Communication Engineering)

한국정보통신학회 논문지 (Journal of the Korea Institute of Information and Communication Engineering)

Current Result Document : 9 / 32 이전건 다음건

한글제목(Korean Title)	선분 그래프의 정점 연결성에 대한 완전 동적 알고리즘
영문제목(English Title)	Fully Dynamic Algorithm for the Vertex Connectivity of Interval Graphs
저자(Author)	김재훈 Jae-hoon Kim
원문수록처(Citation)	VOL 20 NO. 02 PP. 0415 ~ 0420 (2016. 02)
한글내용 (Korean Abstract)	선분 그래프(interval graph) G=(V,E)는 직선 상의 선분들을 나타내는 정점 집합 V와 간선 (i,j)∈ E는 선분 I와 j가 교차함을 나타내는 간선들의 집합 E로 이루어진다. 본 논문에서는 그래프의 여러 특성 중에서 정점 연결성(vertex connectivity)에 주목한다. 특별히 선분들이 겹쳐지는 모습으로 선분 그래프의 정점 연결성을 나타낸다. 또한 선분 그래프에서 정점이나 간선이 추가 되거나 삭제되는 완전 동적 (fully dynamic) 환경에서 정점 연결성을 계산하는 효율적인 알고리즘을 제안할 것이다. 특별한 형태의 선분 트리(interval tree)를 사용하여 새로운 선분이 추가되거나 삭제되는 상황 하에서 정점 연결성을 계산하고 트리를 유지하는데 O(logn) 시간이 소요됨을 보일 것이다.
영문내용 (English Abstract)	A graph G=(V,E) is called an interval graph with a set V of vertices representing intervals on a line such that there is an edge(i,j) ∈ E if and only if intervals i and j intersect. In this paper, we are concerned in the vertex connectivity, one of various characteristics of the graph. Specifically, the vertex connectivity of an interval graph is represented by the overlapping of intervals. Also we propose an efficient algorithm to compute the vertex connectivity on the fully dynamic environment in which the vertices or the edges are inserted or deleted. Using a special kind of interval tree, we show how to compute the vertex connectivity and to maintain the tree in O(logn) time when a new interval is added or an existing interval is deleted.
키워드(Keyword)	선분 그래프 정점 연결성 완전 동적 선분 트리 알고리즘 선분 interval graph vertex connectivity fully dynamic interval tree algorithm interval
파일첨부	PDF 다운로드