Large independent sets in random regular graphs

被引：10

作者：

Duckworth, William ^{[2
]}

Zito, Michele ^{[1
]}

机构：

[1] Univ Liverpool, Dept Comp Sci, Liverpool L69 3BX, Merseyside, England

[2] Australian Natl Univ, Inst Math Sci, Canberra, ACT 0200, Australia

来源：

THEORETICAL COMPUTER SCIENCE | 2009年 / 410卷 / 50期

关键词：

Random graphs; Independent sets; Approximation algorithms; APPROXIMATION ALGORITHMS; NUMBER; HARD;

D O I：

10.1016/j.tcs.2009.08.025

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We present algorithmic lower bounds on the size s(d) of the largest independent sets of vertices in random d-regular graphs, for each fixed d >= 3. For instance, for d = 3 we prove that, for graphs on n vertices, s(d) >= 0.43475n with probability approaching one as n tends to infinity. (C) 2009 Published by Elsevier B.V.

引用

页码：5236 / 5243

页数：8

共 22 条

[1] Polynomial algorithm for finding the largest independent sets in graphs without forks
Alekseev, VE
[J]. DISCRETE APPLIED MATHEMATICS, 2004, 135 (1-3) : 3 - 16
[2] [Anonymous], 1979, COMPUT INTRACTABILIT
[3] Assiyatun H, 2005, LECT NOTES COMPUT SC, V3330, P44
[4] ASSIYATUN H, 2002, THESIS U MELBOURNE
[5] 3-star factors in random d-regular graphs
Assiyatun, Hilda
Wormald, Nicholas
[J]. EUROPEAN JOURNAL OF COMBINATORICS, 2006, 27 (08) : 1249 - 1262
[6] APPROXIMATION ALGORITHMS FOR NP-COMPLETE PROBLEMS ON PLANAR GRAPHS
BAKER, BS
[J]. JOURNAL OF THE ACM, 1994, 41 (01) : 153 - 180
[7] On approximation properties of the independent set problem for low degree graphs
Berman, P
Fujito, T
[J]. THEORY OF COMPUTING SYSTEMS, 1999, 32 (02) : 115 - 132
[8] BOLLOBAS B, 1976, MATH PROC CAMBRIDGE, V80, P419, DOI 10.1017/S0305004100053056
[9] Approximation algorithms for independent sets in map graphs
Chen, ZZ
[J]. JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC, 2001, 41 (01): : 20 - 40
[10] ON THE INDEPENDENCE NUMBER OF RANDOM CUBIC GRAPHS
FRIEZE, A
SUEN, S
[J]. RANDOM STRUCTURES & ALGORITHMS, 1994, 5 (05) : 649 - 664

← 1 2 3 →