A generalized hypergreedy algorithm for weighted perfect matching

Celina Imielinska, Bahman Kalantari

Research output: Contribution to journalArticle

Abstract

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 log n-approximate perfect matching heuristic for points in the Euclidean plane, in O(n log2n) time.

Original languageEnglish (US)
Pages (from-to)177-189
Number of pages13
JournalBIT
Volume33
Issue number2
DOIs
StatePublished - Jun 1 1993

Fingerprint

Perfect Matching
Triangle inequality
Euclidean plane
Weighted Graph
Heuristics
Generalization

All Science Journal Classification (ASJC) codes

  • Software
  • Computer Graphics and Computer-Aided Design
  • Computational Mathematics
  • Applied Mathematics

Cite this

Imielinska, Celina ; Kalantari, Bahman. / A generalized hypergreedy algorithm for weighted perfect matching. In: BIT. 1993 ; Vol. 33, No. 2. pp. 177-189.
@article{adc3ac917a574bb690f4bd1e949286bf,
title = "A generalized hypergreedy algorithm for weighted perfect matching",
abstract = "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 log n-approximate perfect matching heuristic for points in the Euclidean plane, in O(n log2n) time.",
author = "Celina Imielinska and Bahman Kalantari",
year = "1993",
month = "6",
day = "1",
doi = "10.1007/BF01989743",
language = "English (US)",
volume = "33",
pages = "177--189",
journal = "BIT",
issn = "0006-3835",
publisher = "Springer Netherlands",
number = "2",

}

A generalized hypergreedy algorithm for weighted perfect matching. / Imielinska, Celina; Kalantari, Bahman.

In: BIT, Vol. 33, No. 2, 01.06.1993, p. 177-189.

Research output: Contribution to journalArticle

TY - JOUR

T1 - A generalized hypergreedy algorithm for weighted perfect matching

AU - Imielinska, Celina

AU - Kalantari, Bahman

PY - 1993/6/1

Y1 - 1993/6/1

N2 - 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 log n-approximate perfect matching heuristic for points in the Euclidean plane, in O(n log2n) time.

AB - 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 log n-approximate perfect matching heuristic for points in the Euclidean plane, in O(n log2n) time.

UR - http://www.scopus.com/inward/record.url?scp=34250078500&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=34250078500&partnerID=8YFLogxK

U2 - 10.1007/BF01989743

DO - 10.1007/BF01989743

M3 - Article

VL - 33

SP - 177

EP - 189

JO - BIT

JF - BIT

SN - 0006-3835

IS - 2

ER -