인터벌 그래프 컬러링 역문제에 관한 연구
Notes On Inverse Interval Graph Coloring Problems
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
In this paper, we study a polynomially solvable case of the inverse interval graph coloring problem. Given an interval graph associated with a specific interval system, the inverse interval graph coloring problem is defined with the assumption that there is no proper K-coloring for the given interval graph, where K is a fixed integer. The problem is to modify the system of intervals associated with the given interval graph by shifting some of the intervals in such a way that the resulting interval graph becomes K-colorable and the total modification is minimum with respect to a certain norm. In this paper, we focus on the case K=1 where all intervals associated with the interval graph have length 1 or 2, and interval displacement is only allowed to the righthand side with respect to its original position. To solve this problem in polynomial time, we propose a two-phase algorithm which consists of the sorting and First Fit procedure.
Abstract
In this paper, we study a polynomially solvable case of the inverse interval graph coloring problem. Given an interval graph associated with a specific interval system, the inverse interval graph coloring problem is defined with the assumption that there is no proper K-coloring for the given interval graph, where K is a fixed integer. The problem is to modify the system of intervals associated with the given interval graph by shifting some of the intervals in such a way that the resulting interval graph becomes K-colorable and the total modification is minimum with respect to a certain norm. In this paper, we focus on the case K=1 where all intervals associated with the interval graph have length 1 or 2, and interval displacement is only allowed to the righthand side with respect to its original position. To solve this problem in polynomial time, we propose a two-phase algorithm which consists of the sorting and First Fit procedure.
참고문헌 (14)
- M. R. Garey, "Computers and Intractability-A Guide to The Theory of NP-completeness" (1979), Freeman
- M. Cangalovic, "Exact Coloring Algorithms for Weighted Graphs Applied to Timetabling Problems with Lectures of Different Lengths", European Journal of Operational Research, 51(2), pp.248~258 (1991)
- D. De Werra, "Practice and Theory of Automated Timetabling", pp.296~308 (1996), Springer
- D. De Werra, "The Combinatorics of Timetabling", European Journal of Operational Research, 96(3), pp.504~513 (1997)
- R. K. Ahuja, "Inverse Optimization", Operations Research, 49(5), pp.771~783 (2001)
- R. K. Ahuja, "A Faster Algorithm for the Inverse Spanning Tree Problem", Journal of Algorithms, 34(1), pp.177~193 (2000)
- Y. Chung, "On Inverse Traveling Salesman Problems", 4OR-A Quarterly Journal of Operations Research, 10, pp.193~209 (2012)
- Y. Chung, "Notes On Inverse Bin-Packing Problems", Information Processing Letters, 115, pp.60~68 (2015)
- Y. Chung, "Inverse Chromatic Number Problems in Interval and Permutation Graphs", European Journal of Operational Research, 243, pp.763~773 (2015)
- C. Heuberger, "Inverse Combinatorial Optimization : A Survey on Problems, Methods, and Results", Journal of Combinatorial Optimization, 8(3), pp.329~361 (2004)
- M. R. Garey, "One-Processor Scheduling with Symmetric Earliness and Tardiness Penalties", Mathematics of Operations Research, 13, pp.330~348 (1988)
- A.H.G. Rinnooy Kan, "Machine Scheduling Problem:Classification, Complexity and Computation" (1976), Nijhoff
- M. Müller-Hannemann, "Non-Approximabi lity of Just-In-Time Scheduling", Journal of Scheduling, 12(5), pp.555~562 (2009)
- P. Baptiste, "Scheduling Equal-Length Jobs on Identical Parallel Machines", Discrete Applied Mathematics, 103(1-3), pp.21~32 (2000)