Premium
A greedy algorithm for finding a large 2‐matching on a random cubic graph
Author(s) -
Bal Deepak,
Bennett Patrick,
Bohman Tom,
Frieze Alan
Publication year - 2018
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22224
Subject(s) - combinatorics , mathematics , factor critical graph , matching (statistics) , graph factorization , greedy algorithm , graph , random graph , discrete mathematics , line graph , algorithm , graph power , statistics
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 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 1 / 5 ) .