Analysis of a Simple Greedy Matching Algorithm on Random Cubic Graphs

DOI10.1017/S0963548300001474MaRDI QIDQ4844489zbMATH OpenOpenAlexFDO

Authors Stephen Suen, Alan Frieze, Andrew John Radcliffe

Publication date 27 August 1995

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1017/s0963548300001474

zbMATH Keywords

random cubic graphsgreedy matching algorithm

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Random graphs (graph-theoretic aspects) (05C80)

Recommendations

• scientific article; zbMATH DE number 437559
• Small maximal matchings of random cubic graphs
• A greedy algorithm for finding a large 2‐matching on a random cubic graph
• scientific article; zbMATH DE number 1696620
• Randomized greedy matching. II

Cites work

• A Fast Perfect-Matching Algorithm in Random Graphs
• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• Randomized greedy matching
• The asymptotic number of labeled graphs with given degree sequences

Cited in

(11)

• scientific article; zbMATH DE number 1696620 (Why is no real title available?)
• Linear programming and the worst-case analysis of greedy algorithms on cubic graphs
• The average size of maximal matchings in graphs
• A greedy algorithm for finding a large 2‐matching on a random cubic graph
• scientific article; zbMATH DE number 4099072 (Why is no real title available?)
• Finding maximum matchings in random regular graphs in linear expected time
• Small maximal matchings of random cubic graphs
• Greedy matching in bipartite random graphs
• Greedy matching: guarantees and limitations
• Two faces of greedy leaf removal procedure on graphs
• scientific article; zbMATH DE number 437559 (Why is no real title available?)

This page was built for publication: Analysis of a Simple Greedy Matching Algorithm on Random Cubic Graphs

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