An optimal parallel matching algorithm for a convex bipartite graph on a mesh-connected computer

Myung Ho Kim; Chang Sung Jeong

doi:10.1080/10637199508915473

An optimal parallel matching algorithm for a convex bipartite graph on a mesh-connected computer

Myung Ho Kim, Chang Sung Jeong

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

1 Citation (Scopus)

Abstract

In this paper, we address the problem of finding a maximum matching for a convex bipartite graph on a mesh-connected computer (MCC). We shall show that this can be done in optimal time on MCC by designing the efficient merge and division schemes in bottom-up and top-down approach respectively.

Original language	English
Pages (from-to)	15-35
Number of pages	21
Journal	Parallel Algorithms and Applications
Volume	5
Issue number	1-2
DOIs	https://doi.org/10.1080/10637199508915473
Publication status	Published - 1995 Jan 1

Keywords

Convex bipartite graph
Distributed memory model
Maximum matching
Mesh-connected computer
Parallel algorithm

ASJC Scopus subject areas

General Computer Science

Access to Document

10.1080/10637199508915473

Cite this

@article{66677bb0eba44de89e08690ee6782f2c,

title = "An optimal parallel matching algorithm for a convex bipartite graph on a mesh-connected computer",

abstract = "In this paper, we address the problem of finding a maximum matching for a convex bipartite graph on a mesh-connected computer (MCC). We shall show that this can be done in optimal time on MCC by designing the efficient merge and division schemes in bottom-up and top-down approach respectively.",

keywords = "Convex bipartite graph, Distributed memory model, Maximum matching, Mesh-connected computer, Parallel algorithm",

author = "Kim, {Myung Ho} and Jeong, {Chang Sung}",

year = "1995",

month = jan,

day = "1",

doi = "10.1080/10637199508915473",

language = "English",

volume = "5",

pages = "15--35",

journal = "Parallel Algorithms and Applications",

issn = "1063-7192",

publisher = "Taylor and Francis Ltd.",

number = "1-2",

}

TY - JOUR

T1 - An optimal parallel matching algorithm for a convex bipartite graph on a mesh-connected computer

AU - Kim, Myung Ho

AU - Jeong, Chang Sung

PY - 1995/1/1

Y1 - 1995/1/1

N2 - In this paper, we address the problem of finding a maximum matching for a convex bipartite graph on a mesh-connected computer (MCC). We shall show that this can be done in optimal time on MCC by designing the efficient merge and division schemes in bottom-up and top-down approach respectively.

AB - In this paper, we address the problem of finding a maximum matching for a convex bipartite graph on a mesh-connected computer (MCC). We shall show that this can be done in optimal time on MCC by designing the efficient merge and division schemes in bottom-up and top-down approach respectively.

KW - Convex bipartite graph

KW - Distributed memory model

KW - Maximum matching

KW - Mesh-connected computer

KW - Parallel algorithm

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

U2 - 10.1080/10637199508915473

DO - 10.1080/10637199508915473

M3 - Article

AN - SCOPUS:84879121720

SN - 1063-7192

VL - 5

SP - 15

EP - 35

JO - Parallel Algorithms and Applications

JF - Parallel Algorithms and Applications

IS - 1-2

ER -

An optimal parallel matching algorithm for a convex bipartite graph on a mesh-connected computer

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this