Dynamic maximum independent set in proper sets of intervals

Abstract

이 논문에서 우리는 서로 포함하지 않는 실선 구간들의 집합의 최대 독립 부분집합을 유지하고 구간의 추가와 삭제 연산을 지원하는 데이터 구조를 제시한다. 이 데이터 구조는 총 구간의 개수가 n개일때 구간 추가와 삭제 연산, 그리고 최대 독립 부분집합의 크기를 구하는 연산을 각 O(log n) 시간에 지원한다. 우리는 이전 연구 결과와 비슷하게 각 구간의 오른쪽으로의 탐욕 해법을 인코딩한 트리들을 유지한다. 우리는 이전 연구 결과에 변화를 주어 각 노드의 자식 노드들을 오른쪽 끝점 순서대로 정렬하고, 이 임베드된 숲을 오일러 경로 표현법으로 저장한다. 따라서 구간의 추가와 삭제 연산은 오일러 경로 표현법을 구현하는 균형 이진 트리의 join과 split연산 상수 개수로 처리된다.