KJCKorea
Journal Central

@article{ART002517094},
author={Chung Yerim and Hak Jin Kim},
title={Notes On Inverse Interval Graph Coloring Problems},
journal={Journal of The Korea Society of Computer and Information},
issn={1598-849X},
year={2019},
volume={24},
number={10},
pages={57-64},
doi={10.9708/jksci.2019.24.10.057}

TY - JOUR
AU - Chung Yerim
AU - Hak Jin Kim
TI - Notes On Inverse Interval Graph Coloring Problems
JO - Journal of The Korea Society of Computer and Information
PY - 2019
VL - 24
IS - 10
PB - The Korean Society Of Computer And Information
SP - 57
EP - 64
SN - 1598-849X
AB - 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.
KW - Inverse Optimization;Graph Coloring;Interval Graph;Algorithm;Scheduling
DO - 10.9708/jksci.2019.24.10.057
ER -

Chung Yerim and Hak Jin Kim. (2019). Notes On Inverse Interval Graph Coloring Problems. Journal of The Korea Society of Computer and Information, 24(10), 57-64.

Chung Yerim and Hak Jin Kim. 2019, "Notes On Inverse Interval Graph Coloring Problems", Journal of The Korea Society of Computer and Information, vol.24, no.10 pp.57-64. Available from: doi:10.9708/jksci.2019.24.10.057

Chung Yerim, Hak Jin Kim "Notes On Inverse Interval Graph Coloring Problems" Journal of The Korea Society of Computer and Information 24.10 pp.57-64 (2019) : 57.

Chung Yerim, Hak Jin Kim. Notes On Inverse Interval Graph Coloring Problems. 2019; 24(10), 57-64. Available from: doi:10.9708/jksci.2019.24.10.057

Chung Yerim and Hak Jin Kim. "Notes On Inverse Interval Graph Coloring Problems" Journal of The Korea Society of Computer and Information 24, no.10 (2019) : 57-64.doi: 10.9708/jksci.2019.24.10.057

Chung Yerim; Hak Jin Kim. Notes On Inverse Interval Graph Coloring Problems. Journal of The Korea Society of Computer and Information, 24(10), 57-64. doi: 10.9708/jksci.2019.24.10.057

Chung Yerim; Hak Jin Kim. Notes On Inverse Interval Graph Coloring Problems. Journal of The Korea Society of Computer and Information. 2019; 24(10) 57-64. doi: 10.9708/jksci.2019.24.10.057

Chung Yerim, Hak Jin Kim. Notes On Inverse Interval Graph Coloring Problems. 2019; 24(10), 57-64. Available from: doi:10.9708/jksci.2019.24.10.057

Chung Yerim and Hak Jin Kim. "Notes On Inverse Interval Graph Coloring Problems" Journal of The Korea Society of Computer and Information 24, no.10 (2019) : 57-64.doi: 10.9708/jksci.2019.24.10.057