### Abstract

A 2-matching of a graph G is a spanning subgraph with maximum degree two. The size of a 2-matching U is the number of edges in U and this is at least n-k(U) where n is the number of vertices of G and κ denotes the number of components. In this article, we analyze the performance of a greedy algorithm 2greedy for finding a large 2-matching on a random 3-regular graph. We prove that with high probability, the algorithm outputs a 2-matching U with k(U)=Θ(n^{1/5}).

Original language | English |
---|---|

Pages (from-to) | 449-481 |

Number of pages | 33 |

Journal | Journal of Graph Theory |

Volume | 88 |

Issue number | 3 |

DOIs | |

State | Published - Jul 2018 |

### Keywords

- 2-matching
- greedy algorithm
- random cubic graph

## Fingerprint Dive into the research topics of 'A greedy algorithm for finding a large 2-matching on a random cubic graph'. Together they form a unique fingerprint.

## Cite this

Bal, D., Bennett, P., Bohman, T., & Frieze, A. (2018). A greedy algorithm for finding a large 2-matching on a random cubic graph.

*Journal of Graph Theory*,*88*(3), 449-481. https://doi.org/10.1002/jgt.22224