RISS 검색 - 국내학술지논문 상세보기

국문 초록 (Abstract)

이 논문에서는 인터벌 그래프 컬러링 역문제 중 다항시간 안에 풀이 가능한 경우에 대해 연구한다. 인터벌 그래프의 컬러링 역문제는 주어진 인터벌 그래프를 K개의 서로 다른 색깔로 색칠...

이 논문에서는 인터벌 그래프 컬러링 역문제 중 다항시간 안에 풀이 가능한 경우에 대해 연구한다. 인터벌 그래프의 컬러링 역문제는 주어진 인터벌 그래프를 K개의 서로 다른 색깔로 색칠할 수 없는 경우를 가정하며, 다음과 같이 정의된다. 주어진 인터벌 그래프가 K개의 색깔을 이용해서 모두 칠해질 수 있도록 인터벌 그래프와 연관되어 있는 인터벌 시스템을 최소한으로 수정하는 문제이다. 인터벌 시스템에서 두 인터벌이 부분적으로라도 서로 겹쳐있는 구간이 있을 경우 두 인터벌에 해당하는 노드들이 엣지로 연결되어 있음을 의미하고, 따라서 이 경우에는 해당 노드들을 같은 색깔을 이용해 칠할 수 없다. 따라서 겹쳐져 있는 인터벌들을 이동시켜 해당 그래프의 chromatic number를 바꿀 수 있다. 본 논문에서는 인터벌의 길이가 모두 1 또는 2이며, 인터벌의 이동이 본래 위치 대비 오른쪽으로만 가능하다는 제한이 있는 경우에 대해 집중 탐구한다. 이 문제를 해결하는 다항시간 알고리즘으로 sorting과 선입선출 방식을 사용하는 2단계 알고리즘을 제안한다.

다국어 초록 (Multilingual 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.

목차 (Table of Contents)

Abstract
요약
I. Introduction
II. Preliminaries
III. A polynomial-time algorithm solving IBPR₁,₂

Abstract
요약
I. Introduction
II. Preliminaries
III. A polynomial-time algorithm solving IBPR₁,₂
IV. The Proof for Optimality
V. Conclusion
REFERENCES

참고문헌 (Reference)

1 D. De Werra, "The Combinatorics of Timetabling" 96 (96): 504-513, 1997

2 P. Baptiste, "Scheduling Equal-Length Jobs on Identical Parallel Machines" 103 (103): 21-32, 2000

3 D. De Werra, "Practice and Theory of Automated Timetabling" Springer 296-308, 1996

4 M. R. Garey, "One-Processor Scheduling with Symmetric Earliness and Tardiness Penalties" 13 : 330-348, 1988

5 Y. Chung, "On Inverse Traveling Salesman Problems" 10 : 193-209, 2012

6 Y. Chung, "Notes On Inverse Bin-Packing Problems" 115 : 60-68, 2015

7 M. Müller-Hannemann, "Non-Approximabi lity of Just-In-Time Scheduling" 12 (12): 555-562, 2009

8 A.H.G. Rinnooy Kan, "Machine Scheduling Problem:Classification, Complexity and Computation" Nijhoff 1976

9 R. K. Ahuja, "Inverse Optimization" 49 (49): 771-783, 2001

10 C. Heuberger, "Inverse Combinatorial Optimization : A Survey on Problems, Methods, and Results" 8 (8): 329-361, 2004