Analysis of a Simple Greedy Matching Algorithm on Random Cubic Graphs

DOI10.1017/S0963548300001474zbMATH Open0831.90116OpenAlexW2060269923MaRDI QIDQ4844489FDOQ4844489

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

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

zbMATH Keywords

random cubic graphsgreedy matching algorithm

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (11)

• Finding maximum matchings in random regular graphs in linear expected time
• Two faces of greedy leaf removal procedure on graphs
• A greedy algorithm for finding a large 2‐matching on a random cubic graph
• Small maximal matchings of random cubic graphs
• The average size of maximal matchings in graphs
• Greedy matching in bipartite random graphs
• Title not available (Why is that?)
• Linear programming and the worst-case analysis of greedy algorithms on cubic graphs
• Title not available (Why is that?)
• Greedy matching: guarantees and limitations
• Title not available (Why is that?)

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)