RECOGNIZING TOUGH GRAPHS IS NP-HARD

被引：60

作者：

BAUER, D

HAKIMI, SL

SCHMEICHEL, E

机构：

[1] UNIV CALIF DAVIS,DEPT ELECT ENGN & COMP SCI,DAVIS,CA 95616

[2] SAN JOSE STATE UNIV,DEPT MATH & COMP SCI,SAN JOSE,CA 95192

来源：

DISCRETE APPLIED MATHEMATICS | 1990年 / 28卷 / 03期

基金：

美国国家科学基金会;

关键词：

D O I：

10.1016/0166-218X(90)90001-S

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

We show that recognizing 1-tough graphs is NP-hard, thereby settling a long-standing open problem. We also prove it is NP-hard to recognize t-tough graphs for any fixed positive rational number t. © 1990.

引用

页码：191 / 195

页数：5

共 10 条

[1]

Badian E., 1989, Z PAPYROLOGIE EPIGRA, V79, P59

[2]

BONDY JA, 1976, GRAPH THEORY APPLICA

[3]

Chvatal V., 1973, Discrete Mathematics, V5, P215, DOI 10.1016/0012-365X(73)90138-6

[4]

Chvatal V., 1985, TRAVELING SALESMAN P, P403

[5] TOUGHNESS AND THE EXISTENCE OF K-FACTORS [J].

ENOMOTO, H ;

JACKSON, B ;

KATERINIS, P ;

SAITO, A .

JOURNAL OF GRAPH THEORY, 1985, 9 (01) :87-95

[6]

Garey M.R., 1979, COMPUTERS INTRACTABI, V174

[7]

HAGGKVIST R, STRUCTURE NONHAMILTO, V1

[8]

THOMASSEN C, 1981, P LOND MATH SOC, V42, P231

[9]

[No title captured]

[10]

[No title captured]

← 1 →