Greedy Matching on the Line

DOI10.1137/0219045zbMATH Open0697.68035OpenAlexW1995337396WikidataQ57401597 ScholiaQ57401597MaRDI QIDQ3474883FDOQ3474883

Authors: Alan Frieze, Colin McDiarmid, Bruce Reed 

Publication date: 1990

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

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

Recommendations

• scientific article; zbMATH DE number 1003244
• scientific article; zbMATH DE number 1033855
• Randomized greedy matching
• Greedy matching: guarantees and limitations
• Approximation and Online Algorithms
• Max-min greedy matching
• scientific article; zbMATH DE number 7650074
• Online bottleneck matching on a line
• Randomized greedy matching. II

zbMATH Keywords

average caseworst casegreedy matching

Mathematics Subject Classification ID

Geometric probability and stochastic geometry (60D05) Analysis of algorithms and problem complexity (68Q25) 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)

Cited In (9)

• Worst-case greedy matchings in the unitd-cube
• Poisson matching
• Probabilistic Analysis of a Greedy Heuristic for Euclidean Matching
• Greedy matching in Young's lattice
• Title not available (Why is that?)
• Title not available (Why is that?)
• Greedy matching: guarantees and limitations
• Minimal matchings of point processes
• On the existence of weak greedy matching heuristics

This page was built for publication: Greedy Matching on the Line

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