The ACO Seminar (2012-2013)
, 3:30pm, Wean 8220
A greedy algorithm for finding a large 2-matching on a
random cubic graph
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 k
denotes the number of components. The algorithm 2GREEDY is a greedy
algorithm due to Frieze which finds a maximal 2-matching in a graph.
This algorithm is similar to the well known Karp-Sipser algorithm,
which finds ordinary matchings in graphs. We analyze the performance of
2GREEDY on a random 3-regular graph. Our analysis yields (more-or-less)
matching upper and lower bounds on the final number of components. In
particular, we prove that with high probability, the algorithm outputs
a 2-matching U with k(U) = n^(1/5 + o(1)).
Back to the ACO home page