Greedy Matching on the Line

DOI10.1137/0219045zbMath0697.68035OpenAlexW1995337396WikidataQ57401597 ScholiaQ57401597MaRDI QIDQ3474883

Alan M. Frieze, Bruce A. Reed, Colin J. H. McDiarmid

Publication date: 1990

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

Full work available at URL: https://semanticscholar.org/paper/c99c55f48b9c9d30a2f15f41f49a9985ced0db4c

zbMATH Keywords

average caseworst casegreedy matching

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Geometric probability and stochastic geometry (60D05) Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Combinatorial probability (60C05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Related Items

Poisson matching, Minimal matchings of point processes