TY - GEN
T1 - Maximum induced matchings of random cubic graphs
AU - Duckworth, William
AU - Wormald, Nicholas C.
AU - Zito, Michele
PY - 2000
Y1 - 2000
N2 - In this paper we present a heuristic for nding a large induced matching M of cubic graphs. We analyse the performance of this heuristic, which is a random greedy algorithm, on random cubic graphs using dierential equations and obtain a lower bound on the expected size of the induced matching returned by the algorithm. The corresponding upper bound is derived by means of a direct expectation argument. We prove that M asymptotically almost surely satises 0: 2704n ≤|M|≤ 0: 2821n.
AB - In this paper we present a heuristic for nding a large induced matching M of cubic graphs. We analyse the performance of this heuristic, which is a random greedy algorithm, on random cubic graphs using dierential equations and obtain a lower bound on the expected size of the induced matching returned by the algorithm. The corresponding upper bound is derived by means of a direct expectation argument. We prove that M asymptotically almost surely satises 0: 2704n ≤|M|≤ 0: 2821n.
UR - https://www.scopus.com/pages/publications/84957034195
M3 - Conference Paper
AN - SCOPUS:84957034195
SN - 3540677879
SN - 9783540677871
VL - 1858
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 34
EP - 43
BT - Computing and Combinatorics - 6th Annual International Conference, COCOON 2000, Proceedings
PB - Springer-Verlag London Ltd.
T2 - 6th Annual International Conference on Computing and Combinatorics, COCOON 2000
Y2 - 26 July 2000 through 28 July 2000
ER -