MAX-CUT and MAX-BISECTION are NP-hard on unit disk graphs

被引：22
作者：
Diaz, Josep [1 ]
Kaminski, Marcin
机构：
[1] Univ Politecn Catalunya, Lleguatges Sistemes Informat, ES-08034 Barcelona, Spain
[2] Rutgers State Univ, RUTCOR, Piscataway, NJ 08854 USA
来源：
THEORETICAL COMPUTER SCIENCE | 2007年 / 377卷 / 1-3期
关键词：
computational complexity; max-cut; max-bisection; NP-hard; unit disk graphs;
D O I：
10.1016/j.tcs.2007.02.013
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
We prove that the MAX-CUT and MAX-BISECTION problems are NP-hard on unit disk graphs. We also show that X-precision aphs are planar for lambda > 1/root 2- and give a dichotomy theorem for MAX-CUT computational complexity on X-precision unit disk graphs. (c) 2007 Elsevier B.V. All rights reserved.
引用
收藏
页码：271 / 276
页数：6
相关论文
共 15 条
  • [1] Wireless sensor networks: a survey
    Akyildiz, IF
    Su, W
    Sankarasubramaniam, Y
    Cayirci, E
    [J]. COMPUTER NETWORKS, 2002, 38 (04) : 393 - 422
  • [2] Bodlaender H. L., 2000, Nordic Journal of Computing, V7, P14
  • [3] Unit disk graph recognition is NP-hard
    Breu, H
    Kirkpatrick, DG
    [J]. COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 1998, 9 (1-2): : 3 - 24
  • [4] UNIT DISK GRAPHS
    CLARK, BN
    COLBOURN, CJ
    JOHNSON, DS
    [J]. DISCRETE MATHEMATICS, 1990, 86 (1-3) : 165 - 177
  • [5] Approximating layout problems on random geometric graphs
    Diaz, J
    Penrose, MD
    Petit, J
    Serna, M
    [J]. JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC, 2001, 39 (01): : 78 - 116
  • [6] Garey MR, 1979, Computers and Intractablity: A Guide to the Theoryof NP-Completeness
  • [7] Golumbic MC., 1980, Algorithmic Graph Theory and Perfect Graphs
  • [8] Hadlock F., 1975, SIAM Journal on Computing, V4, P221, DOI 10.1137/0204019
  • [9] NC-approximation schemes for NP- and PSPACE-hard problems for geometric graphs
    Hunt, HB
    Marathe, MV
    Radhakrishnan, V
    Ravi, SS
    Rosenkrantz, DJ
    Stearns, RE
    [J]. JOURNAL OF ALGORITHMS, 1998, 26 (02) : 238 - 274
  • [10] Polynomial time approximation schemes for max-bisection on planar and geometric graphs
    Jansen, K
    Karpinski, M
    Lingas, A
    Seidel, E
    [J]. SIAM JOURNAL ON COMPUTING, 2005, 35 (01) : 110 - 119
12