A generalized hypergreedy algorithm for weighted perfect matching | Zendy

Celina Imielińska | Zendy; Bahman Kalantari | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

A generalized hypergreedy algorithm for weighted perfect matching

Author(s) -

Celina Imielińska,

Bahman Kalantari

Publication year - 1993

Publication title -

bit numerical mathematics

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.904

H-Index - 59

eISSN - 1572-9125

pISSN - 0006-3835

DOI - 10.1007/bf01989743

Subject(s) - mathematics , combinatorics , matching (statistics) , generalization , triangle inequality , euclidean geometry , algorithm , heuristic , blossom algorithm , discrete mathematics , mathematical optimization , geometry , mathematical analysis , statistics

We give a generalization of the hypergreedy algorithm for minimum weight perfect matching on a complete edge weighted graph whose weights satisfy the triangle inequality. With a modified version of this algorithm we obtain a logn-approximate perfect matching heuristic for points in the Euclidean plane, inO(n log2n) time.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research