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

DOI10.1002/JGT.22224MaRDI QIDQ4581276zbMATH OpenOpenAlexFDO

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)

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

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)

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}$.

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

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
• scientific article; zbMATH DE number 437559 (Why is no real title available?)
• 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)