Matchings Meeting Quotas and Their Impact on the Blow-Up Lemma

DOI10.1137/S0097539700371053zbMath0989.05092OpenAlexW2060542023WikidataQ124843055 ScholiaQ124843055MaRDI QIDQ2784462

Vojtěch Rödl, Andrzej Ruciński, Michelle Wagner

Publication date: 23 April 2002

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0097539700371053

zbMATH Keywords

randomized algorithmsderandomizationperfect matchingsconditional probabilitiesblow-up lemma\(\varepsilon\)-regular graphs

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Related Items (1)

Spanning 3-colourable subgraphs of small bandwidth in dense graphs

This page was built for publication: Matchings Meeting Quotas and Their Impact on the Blow-Up Lemma