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 条
  • [21] Edge Neighbor Toughness of Graphs
    Feng, Xin
    Wei, Zongtian
    Yang, Yucheng
    AXIOMS, 2022, 11 (06)
  • [22] Toughness and Existence of Fractional (g, f)-factors in Graphs
    Liu, Shuli
    Cai, Jiansheng
    ARS COMBINATORIA, 2009, 93 : 305 - 311
  • [23] Toughness of Kronecker product of graphs
    Guji, Raxida
    Ali, Tursun
    ARS COMBINATORIA, 2016, 127 : 149 - 156
  • [24] Toughness and spectral radius in graphs
    Chen, Yuanyuan
    Fan, Dandan
    Lin, Huiqiu
    DISCRETE MATHEMATICS, 2024, 347 (12)
  • [25] Toughness of the corona of two graphs
    Casablanca, R. M.
    Dianez, A.
    Garica-Vazquez, P.
    INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS, 2011, 88 (13) : 2697 - 2706
  • [26] The spectrum and toughness of regular graphs
    Cioaba, Sebastian M.
    Wong, Wiseley
    DISCRETE APPLIED MATHEMATICS, 2014, 176 : 43 - 52
  • [27] On the toughness of cycle permutation graphs
    Chao, CY
    Han, S
    CZECHOSLOVAK MATHEMATICAL JOURNAL, 2001, 51 (02) : 239 - 260
  • [28] On the Toughness of Cycle Permutation Graphs
    Chao Chong-Yun
    Shaocen Han
    Czechoslovak Mathematical Journal, 2001, 51 (2) : 239 - 260
  • [29] Toughness and [a, b]-factors in graphs
    Chang, Renying
    Zhu, Yan
    Liu, Guizhen
    ARS COMBINATORIA, 2012, 105 : 451 - 456
  • [30] Brief Announcement: Local Approximability of Minimum Dominating Set on Planar Graphs
    Hilke, Miikka
    Lenzen, Christoph
    Suomela, Jukka
    PROCEEDINGS OF THE 2014 ACM SYMPOSIUM ON PRINCIPLES OF DISTRIBUTED COMPUTING (PODC'14), 2014, : 344 - 346
12345