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

Source

Journal of Graph Theory

Type

Journal article

Book Title

Entity type

Access Statement

License Rights

DOI

10.1002/jgt.20434

Restricted until