### 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 |

### Fingerprint

### Keywords

- 2-matching
- greedy algorithm
- random cubic graph

### Cite this

*Journal of Graph Theory*,

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

}

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

**A greedy algorithm for finding a large 2-matching on a random cubic graph.** / Bal, Deepak; Bennett, Patrick; Bohman, Tom; Frieze, Alan.

Research output: Contribution to journal › Article

TY - JOUR

T1 - A greedy algorithm for finding a large 2-matching on a random cubic graph

AU - Bal, Deepak

AU - Bennett, Patrick

AU - Bohman, Tom

AU - Frieze, Alan

PY - 2018/7

Y1 - 2018/7

N2 - 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)=Θ(n1/5).

AB - 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)=Θ(n1/5).

KW - 2-matching

KW - greedy algorithm

KW - random cubic graph

UR - http://www.scopus.com/inward/record.url?scp=85046889991&partnerID=8YFLogxK

U2 - 10.1002/jgt.22224

DO - 10.1002/jgt.22224

M3 - Article

AN - SCOPUS:85046889991

VL - 88

SP - 449

EP - 481

JO - Journal of Graph Theory

JF - Journal of Graph Theory

SN - 0364-9024

IS - 3

ER -