Small Maximal Matchings of Random Cubic Graphs
Date
2009
Authors
Assiyatun, Hilda
Duckworth, William
Journal Title
Journal ISSN
Volume Title
Publisher
Wiley Interscience
Abstract
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 that the size of a smallest maximal matching of a random n-vertex cubic graph is a.a.s. less than 0.3214n. It is known that the size of a smallest maximal matching of a random n-vertex cubic graph is a.a.s. larger than 0.3158n.
Description
Keywords
Keywords: Average-case; Cubic graph; Greedy algorithms; Matchings; Maximal matchings; Differential equations; Packet networks Cubic; Graphs; Matchings; Random
Citation
Collections
Source
Journal of Graph Theory
Type
Journal article