구간 그래프상의 최대 가중치 독립 집합 문제를 위한 효율적인 알고리즘
A new Algorithm for the Maximum Weight Independent Set on Interval Graphs
1
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
In this study, we consider the maximum weight independent set problem on an interval graph. For the problem, linear time algorithms have already been introduced two decades ago. The algorithmshave a common assumption that end points of intervals are distinct and sorted. We propose an efficientlinear time algorithm that works without the assumption for the problem. Computational results applied tolarge-size data set show efficiency of our algorithm.
Abstract
In this study, we consider the maximum weight independent set problem on an interval graph. For the problem, linear time algorithms have already been introduced two decades ago. The algorithmshave a common assumption that end points of intervals are distinct and sorted. We propose an efficientlinear time algorithm that works without the assumption for the problem. Computational results applied tolarge-size data set show efficiency of our algorithm.
참고문헌 (5)
- Chang, M., "Efficient algorithms for the domination problems on interval graph and circular-arc graphs", SIAM Journal on Computing, 27(6), pp.1671~1694 (1998)
- Golumbic, M. C., "Interval graphs and related topics", Discrete Math., 55, pp.113~243 (1985)
- Hsiao, J., "An efficient algorithm for finding a maximum weight 2-independent set on interval graphs", Information Processing Letters, 43, pp.229~235 (1992)
- Kovalyov, Mikhail Y., "Fixed interval scheduling: Models, applications, computational complexity and algorithms", European Journal of Operational Research, 178, pp.331~342 (2007)
- Lee, T., "Optimal Routing and Wavelength Assignment in WDM Ring Networks", IEEE Journal on selected areas in communications, 18(10), pp.2146~2154 (2000)