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

Myung Ho Kim; Chang Sung Jeong

doi:10.1080/10637199508915505

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

Myung Ho Kim, Chang Sung Jeong

School of Electrical Engineering

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

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)	129-141
Number of pages	13
Journal	Parallel Algorithms and Applications
Volume	6
Issue number	2-3
DOIs	https://doi.org/10.1080/10637199508915505
Publication status	Published - 1995 Jan 1

Keywords

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

ASJC Scopus subject areas

Computer Science(all)

Access to Document

10.1080/10637199508915505

Cite this

@article{677139c5d4f94997a09d4ebc36120f74,

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/10637199508915505",

language = "English",

volume = "6",

pages = "129--141",

journal = "International Journal of Parallel, Emergent and Distributed Systems",

issn = "1744-5760",

publisher = "Taylor and Francis Ltd.",

number = "2-3",

}

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=84948866777&partnerID=8YFLogxK

U2 - 10.1080/10637199508915505

DO - 10.1080/10637199508915505

M3 - Article

AN - SCOPUS:84948866777

SN - 1744-5760

VL - 6

SP - 129

EP - 141

JO - International Journal of Parallel, Emergent and Distributed Systems

JF - International Journal of Parallel, Emergent and Distributed Systems

IS - 2-3

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

Cite this