Small Maximal Matchings of Random Cubic Graphs
We consider the expected size of a smallest maximalmatching of cubic graphs. Firstly, we present a randomized greedy algorithm for finding a small maximal matching of cubic graphs.We analyze the averagecase performance of this heuristic on random n-vertex cubic graphs using differential equations. In this way, we prove that the expected size of the maximalmatching returned by the algorithm is asymptotically almost surely (a.a.s.) less than 0.34623n. We also give an existence proof which shows...[Show more]
|Collections||ANU Research Publications|
|Source:||Journal of Graph Theory|
Items in Open Research are protected by copyright, with all rights reserved, unless otherwise indicated.