Maximum induced matchings of random cubic graphs

W. Duckworth; N. C. Wormald; M. Zito

doi:10.1016/S0377-0427(01)00457-5

Maximum induced matchings of random cubic graphs

W. Duckworth, N. C. Wormald, M. Zito

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

10 Citations (Scopus)

Abstract

We present a heuristic for finding a large induced matching of cubic graphs. We analyse the performance of this heuristic, which is a random greedy algorithm, on random cubic graphs using differential equations and obtain a lower bound on the expected size of the induced matching. M, returned by the algorithm. A corresponding upper bound is derived by means of a direct expectation argument. We prove that M asymptotically almost surely satisfies 0.270413n ≤ M ≤ 0.282069n.

Original language	English
Pages (from-to)	39-50
Number of pages	12
Journal	Journal of Computational and Applied Mathematics
Volume	142
Issue number	1
DOIs	https://doi.org/10.1016/S0377-0427(01)00457-5
Publication status	Published - 1 May 2002
Externally published	Yes

Access to Document

10.1016/S0377-0427(01)00457-5

Cite this

@article{aef51e5452a54c42a4bc8ad48c56a659,

title = "Maximum induced matchings of random cubic graphs",

abstract = "We present a heuristic for finding a large induced matching of cubic graphs. We analyse the performance of this heuristic, which is a random greedy algorithm, on random cubic graphs using differential equations and obtain a lower bound on the expected size of the induced matching. M, returned by the algorithm. A corresponding upper bound is derived by means of a direct expectation argument. We prove that M asymptotically almost surely satisfies 0.270413n ≤ M ≤ 0.282069n.",

author = "W. Duckworth and Wormald, \{N. C.\} and M. Zito",

year = "2002",

month = may,

day = "1",

doi = "10.1016/S0377-0427(01)00457-5",

language = "English",

volume = "142",

pages = "39--50",

journal = "Journal of Computational and Applied Mathematics",

issn = "0377-0427",

publisher = "Elsevier BV",

number = "1",

}

TY - JOUR

T1 - Maximum induced matchings of random cubic graphs

AU - Duckworth, W.

AU - Wormald, N. C.

AU - Zito, M.

PY - 2002/5/1

Y1 - 2002/5/1

N2 - We present a heuristic for finding a large induced matching of cubic graphs. We analyse the performance of this heuristic, which is a random greedy algorithm, on random cubic graphs using differential equations and obtain a lower bound on the expected size of the induced matching. M, returned by the algorithm. A corresponding upper bound is derived by means of a direct expectation argument. We prove that M asymptotically almost surely satisfies 0.270413n ≤ M ≤ 0.282069n.

AB - We present a heuristic for finding a large induced matching of cubic graphs. We analyse the performance of this heuristic, which is a random greedy algorithm, on random cubic graphs using differential equations and obtain a lower bound on the expected size of the induced matching. M, returned by the algorithm. A corresponding upper bound is derived by means of a direct expectation argument. We prove that M asymptotically almost surely satisfies 0.270413n ≤ M ≤ 0.282069n.

UR - https://www.scopus.com/pages/publications/0036566137

U2 - 10.1016/S0377-0427(01)00457-5

DO - 10.1016/S0377-0427(01)00457-5

M3 - Article

AN - SCOPUS:0036566137

SN - 0377-0427

VL - 142

SP - 39

EP - 50

JO - Journal of Computational and Applied Mathematics

JF - Journal of Computational and Applied Mathematics

IS - 1

ER -

Maximum induced matchings of random cubic graphs

Abstract

Access to Document

Other files and links

Cite this