共 68 条
[1]
Asdre K(2007)The harmonious coloring problem is NP-complete for interval and permutation graphs Discrete Appl. Math. 155 2377-2382
[2]
Ioannidou K(1983)The max-cut problem on graphs not contractible to Oper. Res. Lett. 2 107-111
[3]
Nikolopoulos SD(1988)An application of combinatorial optimization to statistical physics and circuit layout design Oper. Res. 36 493-513
[4]
Barahona F(1989)Achromatic number is NP-complete for cographs and interval graphs Inform. Process. Lett. 31 135-138
[5]
Barahona F(2000)On the complexity of the maximum cut problem Nordic J. Comput. 7 14-31
[6]
Grötschel M(2017)A polynomial-time algorithm for the maximum cardinality cut problem in proper interval graphs Inform. Process. Lett. 121 29-33
[7]
Jünger M(1998)Efficient algorithms for the domination problems on interval and circular-arc graphs SIAM J. Comput. 27 1671-1694
[8]
Reinelt G(2015)Max-cut parameterized above the Edwards–Erdős bound Algorithmica 72 734-757
[9]
Bodlaender HL(2007)MAX-CUT and MAX-BISECTION are NP-hard on unit disk graphs Theoret. Comput. Sci. 377 271-276
[10]
Bodlaender HL(2014)Almost optimal lower bounds for problems parameterized by clique-width SIAM J. Comput. 43 1541-1563