Large independent sets in random regular graphs

William Duckworth; Michele Zito

doi:10.1016/j.tcs.2009.08.025

Large independent sets in random regular graphs

William Duckworth, Michele Zito^*

^*Corresponding author for this work

Research output: Contribution to journal › Article › peer-review

12 Citations (Scopus)

Abstract

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.43475 n with probability approaching one as n tends to infinity.

Original language	English
Pages (from-to)	5236-5243
Number of pages	8
Journal	Theoretical Computer Science
Volume	410
Issue number	50
DOIs	https://doi.org/10.1016/j.tcs.2009.08.025
Publication status	Published - 17 Nov 2009

Access to Document

10.1016/j.tcs.2009.08.025

Cite this

@article{37d68cf978ba407ba33c03f52f841158,

title = "Large independent sets in random regular graphs",

abstract = "We present algorithmic lower bounds on the size sd 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, sd ≥ 0.43475 n with probability approaching one as n tends to infinity.",

keywords = "Approximation algorithms, Independent sets, Random graphs",

author = "William Duckworth and Michele Zito",

year = "2009",

month = nov,

day = "17",

doi = "10.1016/j.tcs.2009.08.025",

language = "English",

volume = "410",

pages = "5236--5243",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier B.V.",

number = "50",

}

TY - JOUR

T1 - Large independent sets in random regular graphs

AU - Duckworth, William

AU - Zito, Michele

PY - 2009/11/17

Y1 - 2009/11/17

N2 - We present algorithmic lower bounds on the size sd 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, sd ≥ 0.43475 n with probability approaching one as n tends to infinity.

AB - We present algorithmic lower bounds on the size sd 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, sd ≥ 0.43475 n with probability approaching one as n tends to infinity.

KW - Approximation algorithms

KW - Independent sets

KW - Random graphs

UR - http://www.scopus.com/inward/record.url?scp=70349754672&partnerID=8YFLogxK

U2 - 10.1016/j.tcs.2009.08.025

DO - 10.1016/j.tcs.2009.08.025

M3 - Article

SN - 0304-3975

VL - 410

SP - 5236

EP - 5243

JO - Theoretical Computer Science

JF - Theoretical Computer Science

IS - 50

ER -

Large independent sets in random regular graphs

Abstract

Access to Document

Other files and links

Fingerprint

Cite this