A greedy algorithm for finding a large 2‐matching on a random cubic graph. Issue 3 (27th November 2017)

• Record Type: Journal Article
• Authors: Bal, Deepak; Bennett, Patrick; Bohman, Tom; Frieze, Alan
• Is Part Of: Journal of graph theory. Volume 88:Issue 3(2018)
• Page Start: 449
• Page End: 481
• Publication Date: 2017-11-27
• Subjects: greedy algorithm -- 2‐matching -- random cubic graph; Graph theory -- Periodicals; 511
• DOI: 10.1002/jgt.22224
• Languages: English
• ISSNs: 0364-9024

Abstract

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 − κ ( 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 algorithm2greedy 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 1 / 5 ) .