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 [J].

Akyildiz, IF ;

Su, W ;

Sankarasubramaniam, Y ;

Cayirci, E .

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 [J].

Breu, H ;

Kirkpatrick, DG .

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 1998, 9 (1-2) :3-24

[4] UNIT DISK GRAPHS [J].

CLARK, BN ;

COLBOURN, CJ ;

JOHNSON, DS .

DISCRETE MATHEMATICS, 1990, 86 (1-3) :165-177

[5] Approximating layout problems on random geometric graphs [J].

Diaz, J ;

Penrose, MD ;

Petit, J ;

Serna, M .

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 [J].

Hunt, HB ;

Marathe, MV ;

Radhakrishnan, V ;

Ravi, SS ;

Rosenkrantz, DJ ;

Stearns, RE .

JOURNAL OF ALGORITHMS, 1998, 26 (02) :238-274

[10] Polynomial time approximation schemes for max-bisection on planar and geometric graphs [J].

Jansen, K ;

Karpinski, M ;

Lingas, A ;

Seidel, E .

SIAM JOURNAL ON COMPUTING, 2005, 35 (01) :110-119

← 1 2 →