Notes On Inverse Interval Graph Coloring Problems

Chung Yerim; Hak Jin Kim

doi:https://doi.org/10.9708/jksci.2019.24.10.057

Journal of The Korea Society of Computer and Information

Abbr : JKSCI
2019, 24(10), pp.57-64
DOI :https://doi.org/10.9708/jksci.2019.24.10.057
Publisher : The Korean Society Of Computer And Information
Research Area : Computer Science

Chung Yerim ¹ , Hak Jin Kim ²

¹ 연세대학교
² 연세대학교

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.
KEYWORDS

Inverse Optimization , Graph Coloring , Interval Graph , Algorithm , Scheduling
REFERENCES (14)

[book] M. R. Garey / 1979 / Computers and Intractability-A Guide to The Theory of NP-completeness / Freeman

[journal] M. Cangalovic / 1991 / Exact Coloring Algorithms for Weighted Graphs Applied to Timetabling Problems with Lectures of Different Lengths / European Journal of Operational Research 51 (2) : 248~258

[book] D. De Werra / 1996 / Practice and Theory of Automated Timetabling / Springer : 296~308

[journal] D. De Werra / 1997 / The Combinatorics of Timetabling / European Journal of Operational Research 96 (3) : 504~513

[journal] R. K. Ahuja / 2001 / Inverse Optimization / Operations Research 49 (5) : 771~783

[journal] R. K. Ahuja / 2000 / A Faster Algorithm for the Inverse Spanning Tree Problem / Journal of Algorithms 34 (1) : 177~193

[journal] Y. Chung / 2012 / On Inverse Traveling Salesman Problems / 4OR-A Quarterly Journal of Operations Research 10 : 193~209

[journal] Y. Chung / 2015 / Notes On Inverse Bin-Packing Problems / Information Processing Letters 115 : 60~68

[journal] Y. Chung / 2015 / Inverse Chromatic Number Problems in Interval and Permutation Graphs / European Journal of Operational Research 243 : 763~773

[journal] C. Heuberger / 2004 / Inverse Combinatorial Optimization : A Survey on Problems, Methods, and Results / Journal of Combinatorial Optimization 8 (3) : 329~361

[journal] M. R. Garey / 1988 / One-Processor Scheduling with Symmetric Earliness and Tardiness Penalties / Mathematics of Operations Research 13 : 330~348

[book] A.H.G. Rinnooy Kan / 1976 / Machine Scheduling Problem:Classification, Complexity and Computation / Nijhoff

[journal] M. Müller-Hannemann / 2009 / Non-Approximabi lity of Just-In-Time Scheduling / Journal of Scheduling 12 (5) : 555~562

[journal] P. Baptiste / 2000 / Scheduling Equal-Length Jobs on Identical Parallel Machines / Discrete Applied Mathematics 103 (1-3) : 21~32
KCI Citation (0)

KJC Korea
Journal Central

Statistics

Tools