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

来源：

关键词：

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
Asdre, Katerina
Ioannidou, Kyriaki
Nikolopoulos, Stavros D.
[J]. DISCRETE APPLIED MATHEMATICS, 2007, 155 (17) : 2377 - 2382
[5] AN APPLICATION OF COMBINATORIAL OPTIMIZATION TO STATISTICAL PHYSICS AND CIRCUIT LAYOUT DESIGN
BARAHONA, F
GROTSCHEL, M
JUNGER, M
REINELT, G
[J]. OPERATIONS RESEARCH, 1988, 36 (03) : 493 - 513
[6] THE MAX-CUT PROBLEM ON GRAPHS NOT CONTRACTIBLE TO K5
BARAHONA, F
[J]. 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