A greedy algorithm for finding a large 2‐matching on a random cubic graph

DOI10.1002/JGT.22224zbMATH Open1393.05238arXiv1209.6570OpenAlexW2963956266MaRDI QIDQ4581276FDOQ4581276

Authors: Deepak Bal, Patrick Bennett, Tom Bohman, Alan Frieze 

Publication date: 16 August 2018

Published in: Journal of Graph Theory (Search for Journal in Brave)

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-k(U)$ where $n$ is the number of vertices of $G$ and $k$ denotes the number of components. In this paper, we analyze the performance of a greedy algorithm extsc{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 $k(U)=ildeThetaof{n}^{1/5}$.

Full work available at URL: https://arxiv.org/abs/1209.6570

Recommendations

• scientific article; zbMATH DE number 437559
• Analysis of a Simple Greedy Matching Algorithm on Random Cubic Graphs
• scientific article; zbMATH DE number 1033855
• On a greedy 2-matching algorithm and Hamilton cycles in random graphs with minimum degree at least three
• A Fast Perfect-Matching Algorithm in Random Graphs
• Greedy matching in bipartite random graphs
• Finding maximum matchings in random regular graphs in linear expected time
• Randomized greedy algorithms for independent sets and matchings in regular graphs: exact results and finite girth corrections

zbMATH Keywords

greedy algorithm2-matchingrandom cubic graph

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cited In (5)

• An almost-greedy search on random binary vectors and random graphs
• Analysis of a Simple Greedy Matching Algorithm on Random Cubic Graphs
• A natural barrier in random greedy hypergraph matching
• Title not available (Why is that?)
• On a greedy 2-matching algorithm and Hamilton cycles in random graphs with minimum degree at least three

This page was built for publication: A greedy algorithm for finding a large 2‐matching on a random cubic graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4581276)