DocumentCode
1832611
Title
An optimal parallel matching algorithm for a convex bipartite graph on a mesh-connected computer
Author
Kim, Myung-Ho ; Jeong, Chang-Sung ; Kim, Myung-Soo
Author_Institution
Dept. of Comput. Sci., POSTECH, Pohang, South Korea
fYear
1994
fDate
26-29 Apr 1994
Firstpage
229
Lastpage
233
Abstract
We address the problem of finding a maximum matching for a convex bipartite graph on a mesh-connected computer (MCC). We 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
computational complexity; computational geometry; distributed memory systems; graph theory; parallel algorithms; bottom-up; convex bipartite graph; distributed memory; graph problems; mesh-connected computer; optimal parallel matching algorithm; top-down approach; Algorithm design and analysis; Artificial intelligence; Bipartite graph; Computer science; Concurrent computing; Distributed computing; Parallel algorithms; Partitioning algorithms; Solid modeling; Sorting;
fLanguage
English
Publisher
ieee
Conference_Titel
Parallel Processing Symposium, 1994. Proceedings., Eighth International
Conference_Location
Cancun
Print_ISBN
0-8186-5602-6
Type
conf
DOI
10.1109/IPPS.1994.288296
Filename
288296
Link To Document