The Average Performance of the Greedy Matching Algorithm

Open Access

Publisher Website

1 May 1993

journal article
Published by Institute of Mathematical Statistics in The Annals of Applied Probability

Vol. 3 (2), 526-552
https://doi.org/10.1214/aoap/1177005436

Abstract

This paper we discuss the expected performance of the simplest of matchingalgorithms i.e. the GREEDY (or myopic) algorithm. Given a graph G the

Keywords

Cited by 24 articles