지원사업
학술연구/단체지원/교육 등 연구자 활동을 지속하도록 DBpia가 지원하고 있어요.
커뮤니티
연구자들이 자신의 연구와 전문성을 널리 알리고, 새로운 협력의 기회를 만들 수 있는 네트워킹 공간이에요.
이용수
이 논문의 연구 히스토리 (3)
- 이 논문의 후속연구가 궁금하신가요?
- 연관 학술논문 또는 학술발표를 통해 보다 발전된 연구결과를 확인하실 수 있습니다.
- 이 논문의 연구 히스토리 확인하기
초록· 키워드
오류제보하기
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. / 1998 / Efficient algorithms for the domination problems on interval graph and circular-arc graphs / SIAM Journal on Computing 27(6):1671~1694
Golumbic, M. C. / 1985 / Interval graphs and related topics / Discrete Math. 55:113~243
Hsiao, J. / 1992 / An efficient algorithm for finding a maximum weight 2-independent set on interval graphs / Information Processing Letters 43:229~235
Kovalyov, Mikhail Y. / 2007 / Fixed interval scheduling: Models, applications, computational complexity and algorithms / European Journal of Operational Research 178:331~342
Lee, T. / 2000 / Optimal Routing and Wavelength Assignment in WDM Ring Networks / IEEE Journal on selected areas in communications 18(10):2146~2154
Golumbic, M. C. / 1985 / Interval graphs and related topics / Discrete Math. 55:113~243
Hsiao, J. / 1992 / An efficient algorithm for finding a maximum weight 2-independent set on interval graphs / Information Processing Letters 43:229~235
Kovalyov, Mikhail Y. / 2007 / Fixed interval scheduling: Models, applications, computational complexity and algorithms / European Journal of Operational Research 178:331~342
Lee, T. / 2000 / Optimal Routing and Wavelength Assignment in WDM Ring Networks / IEEE Journal on selected areas in communications 18(10):2146~2154
이 논문의 저자 정보
최근 본 자료
댓글(0)
0