A greedy algorithm for finding a large 2-matching on a random cubic graph
Bal, Deepak · Bennett, Patrick · Bohman, Tom · Frieze, Alan
Original · EN
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-(U) where n is the number of vertices of G and denotes the number of components. In this paper, 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 (U) = Θn¹/⁵.
English translation
This paper has no Arabic translation yet. Be the first: it takes a few seconds, and the result is stored for every future reader.