scientific article; zbMATH DE number 1512672

MaRDI QIDQ4508359zbMATH OpenFDO

Authors Michele Zito

Publication date 21 June 2001

zbMATH Keywords

maximal matchingrandom graphs

Mathematics Subject Classification ID

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

Recommendations

• Small maximal matchings in random graphs.
• Small maximal matchings of random cubic graphs
• Random matchings in regular graphs
• Finding maximum matchings in random regular graphs in linear expected time
• Matching algorithms are fast in sparse random graphs

Cited in

(15)

• The number of matchings in random regular graphs and bipartite graphs
• Maximum matchings in a class of random graphs
• Small maximal matchings in random graphs.
• Randomized approximation of the stable marriage problem
• Perfect matchings in \(\varepsilon\)-regular graphs and the blow-up lemma
• Karp-Sipser on random graphs with a fixed degree sequence
• scientific article; zbMATH DE number 2127722 (Why is no real title available?)
• Maximum matchings in random bipartite graphs and the space utilization of cuckoo hash tables
• Small maximal matchings of random cubic graphs
• scientific article; zbMATH DE number 1929931 (Why is no real title available?)
• Largest planar matching in random bipartite graphs
• scientific article; zbMATH DE number 825131 (Why is no real title available?)
• A linear algorithm for computing of a minimum weight maximal induced matching in an edge-weighted tree
• Finding maximum matchings in random regular graphs in linear expected time
• The average size of maximal matchings in graphs

This page was built for publication:

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