Complexity of Maximum Cut on Interval Graphs

被引：3
作者：
Adhikary, Ranendu [1 ]
Bose, Kaustav [2 ]
Mukherjee, Satwik [1 ]
Roy, Bodhayan [3 ]
机构：
[1] Jadavpur Univ, Kolkata, India
[2] Indian Stat Inst, Kolkata, India
[3] Indian Inst Technol Kharagpur, Kharagpur, India
来源：
DISCRETE & COMPUTATIONAL GEOMETRY | 2023年 / 70卷 / 02期
关键词：
Maximum cut; Interval graph; NP-complete; MAX-CUT; EFFICIENT ALGORITHMS; NP-COMPLETENESS; TIME ALGORITHM; APPROXIMATION; OPTIMIZATION; CLIQUE;
D O I：
10.1007/s00454-022-00472-y
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
We resolve the longstanding open problem concerning the computational complexity of MaxCut on interval graphs by showing that it is NP-complete.
引用
收藏
页码：307 / 322
页数：16
相关论文
共 47 条
[1]  
Adhikary R., 2020, ARXIV
[2]  
Adhikary R., 2021, 37 INT S COMPUTATION, V189
[3]  
[Anonymous], 1978, Food Webs and Niche Space
[4]   The harmonious coloring problem is NP-complete for interval and permutation graphs [J].
Asdre, Katerina ;
Ioannidou, Kyriaki ;
Nikolopoulos, Stavros D. .
DISCRETE APPLIED MATHEMATICS, 2007, 155 (17) :2377-2382
[5]   AN APPLICATION OF COMBINATORIAL OPTIMIZATION TO STATISTICAL PHYSICS AND CIRCUIT LAYOUT DESIGN [J].
BARAHONA, F ;
GROTSCHEL, M ;
JUNGER, M ;
REINELT, G .
OPERATIONS RESEARCH, 1988, 36 (03) :493-513
[6]   THE MAX-CUT PROBLEM ON GRAPHS NOT CONTRACTIBLE TO K5 [J].
BARAHONA, F .
OPERATIONS RESEARCH LETTERS, 1983, 2 (03) :107-111
[7]  
Berman P., 1999, Automata, Languages and Programming. 26th International Colloquium, ICALP'99. Proceedings (Lecture Notes in Computer Science Vol.1644), P200
[8]  
Bodlaender H. L., 2000, Nordic Journal of Computing, V7, P14
[9]  
Bodlaender H. L., 1999, Electron. Notes Discret. Math., V3, P19, DOI DOI 10.1016/S1571-0653(05)80014-9
[10]  
Bodlaender HL, 2004, LECT NOTES COMPUT SC, V3059, P87
12345