A note on the approximability of the toughness of graphs

被引：0

作者：

Bazgan, C ^{[1
]}

机构：

[1] Univ Paris 09, LAMSADE, F-75775 Paris, France

来源：

DISCRETE MATHEMATICS | 2004年 / 280卷 / 1-3期

关键词：

toughness; graph; approximation algorithm; complexity;

D O I：

10.1016/j.disc.2003.10.013

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

We show that, if NP not equal ZPP, for any epsilon > 0, the toughness of a graph with n vertices is not approximable in polynomial time within a factor of (1)/(2) (n/2)(1-epsilon). We give a 4-approximation for graphs with toughness bounded by (1)/(3) and we show that this result cannot be generalized to graphs with a bounded toughness. More exactly we prove that there is no constant approximation for graphs with bounded toughness, unless P = NP. (C) 2003 Elsevier B.V. All rights reserved.

引用

页码：215 / 218

页数：4

共 50 条

[1] TOUGHNESS, ISOLATED TOUGHNESS AND PATH FACTORS IN GRAPHS
Zhou, Sizhong
Wu, Jiancheng
Xu, Yang
BULLETIN OF THE AUSTRALIAN MATHEMATICAL SOCIETY, 2022, 106 (02) : 195 - 202
[2] Approximability of partitioning graphs with supply and demand
Ito, Takehiro
Demaine, Erik D.
Zhou, Xiao
Nishizeki, Takao
JOURNAL OF DISCRETE ALGORITHMS, 2008, 6 (04) : 627 - 650
[3] A note on the approximability of cutting stock problems
Cintra, G. F.
Miyazawa, F. K.
Wakabayashi, Y.
Xavier, E. C.
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2007, 183 (03) : 1328 - 1332
[4] Conjunctive Queries on Probabilistic Graphs: The Limits of Approximability
Amarilli, Antoine
van Bremen, Timothy
Meel, Kuldeep S.
27TH INTERNATIONAL CONFERENCE ON DATABASE THEORY, ICDT 2024, 2024, 290
[5] On the Parameterized Approximability of Contraction to Classes of Chordal Graphs
Gunda, Spoorthy
Jain, Pallavi
Lokshtanov, Daniel
Saurabh, Saket
Tale, Prafullkumar
ACM TRANSACTIONS ON COMPUTATION THEORY, 2021, 13 (04)
[6] Approximability of the Distance Independent Set Problem on Regular Graphs and Planar Graphs
Eto, Hiroshi
Ito, Takehiro
Liu, Zhilong
Miyano, Eiji
IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES, 2022, E105A (09) : 1211 - 1222
[7] Toughness and (a, b, k)-critical graphs
Zhou, Sizhong
Jiang, Jiashang
INFORMATION PROCESSING LETTERS, 2011, 111 (09) : 403 - 407
[8] Approximability of the minimum maximal matching problem in planar graphs
Nagamochi, H
Nishida, Y
Ibaraki, T
IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES, 2003, E86A (12): : 3251 - 3258
[9] On approximability of the independent set problem for low degree graphs
Chlebík, M
Chlebíková, J
STRUCTURAL INFORMATION AND COMMUNICATION COMPLEXITY, PROCEEDING, 2004, 3104 : 47 - 56
[10] Toughness in Graphs – A Survey
Douglas Bauer
Hajo Broersma
Edward Schmeichel
Graphs and Combinatorics, 2006, 22 : 1 - 35

← 1 2 3 4 5 →