We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
A greedy algorithm for finding a large 2‐matching on a random cubic graph.
- Authors
Bal, Deepak; Bennett, Patrick; Bohman, Tom; Frieze, Alan
- Abstract
Abstract: A 2‐matching of a graph <italic>G</italic> is a spanning subgraph with maximum degree two. The size of a 2‐matching <italic>U</italic> is the number of edges in <italic>U</italic> and this is at least n − κ ( U ) where <italic>n</italic> is the number of vertices of <italic>G</italic> 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 <italic>U</italic> with κ ( U ) = Θ ∼ ( n 1 / 5 ).
- Subjects
GREEDY algorithms; RANDOM graphs; REGULAR graphs; GRAPH theory; SUBGRAPHS; GEOMETRIC vertices; MATCHING theory
- Publication
Journal of Graph Theory, 2018, Vol 88, Issue 3, p449
- ISSN
0364-9024
- Publication type
Article
- DOI
10.1002/jgt.22224