An efficient parallel algorithm for finding minimum weight matching for points on a convex polygon

Xin He

doi:10.1016/0020-0190(91)90143-6

An efficient parallel algorithm for finding minimum weight matching for points on a convex polygon

Xin He

Department of Computer Science and Engineering

Research output: Contribution to journal › Article › peer-review

3 Scopus citations

Abstract

We present an efficient parallel algorithm for finding a minimum weight perfect matching for points on a convex polygon. where the weight of an edge is the Euclidean distance between its two end points. On a concurrent read exclusive write PRAM, the algorithm runs in O(log²n) time with O(n) processors.

Original language	English
Pages (from-to)	111-116
Number of pages	6
Journal	Information Processing Letters
Volume	37
Issue number	2
DOIs	https://doi.org/10.1016/0020-0190(91)90143-6
State	Published - Jan 31 1991

Keywords

convex polygon
Parallel algorithms
weighted perfect matching

Access to Document

10.1016/0020-0190(91)90143-6

Cite this

@article{d17c4570e5534a2ba5e55546b0bcd66b,

title = "An efficient parallel algorithm for finding minimum weight matching for points on a convex polygon",

abstract = "We present an efficient parallel algorithm for finding a minimum weight perfect matching for points on a convex polygon. where the weight of an edge is the Euclidean distance between its two end points. On a concurrent read exclusive write PRAM, the algorithm runs in O(log2n) time with O(n) processors.",

keywords = "convex polygon, Parallel algorithms, weighted perfect matching",

author = "Xin He",

year = "1991",

month = jan,

day = "31",

doi = "10.1016/0020-0190(91)90143-6",

language = "English",

volume = "37",

pages = "111--116",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier B.V.",

number = "2",

}

TY - JOUR

T1 - An efficient parallel algorithm for finding minimum weight matching for points on a convex polygon

AU - He, Xin

PY - 1991/1/31

Y1 - 1991/1/31

N2 - We present an efficient parallel algorithm for finding a minimum weight perfect matching for points on a convex polygon. where the weight of an edge is the Euclidean distance between its two end points. On a concurrent read exclusive write PRAM, the algorithm runs in O(log2n) time with O(n) processors.

AB - We present an efficient parallel algorithm for finding a minimum weight perfect matching for points on a convex polygon. where the weight of an edge is the Euclidean distance between its two end points. On a concurrent read exclusive write PRAM, the algorithm runs in O(log2n) time with O(n) processors.

KW - convex polygon

KW - Parallel algorithms

KW - weighted perfect matching

UR - https://www.scopus.com/pages/publications/0025894568

U2 - 10.1016/0020-0190(91)90143-6

DO - 10.1016/0020-0190(91)90143-6

M3 - Article

AN - SCOPUS:0025894568

SN - 0020-0190

VL - 37

SP - 111

EP - 116

JO - Information Processing Letters

JF - Information Processing Letters

IS - 2

ER -

An efficient parallel algorithm for finding minimum weight matching for points on a convex polygon

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this