BSP/CGM Algorithm for Maximum Matching in Convex Bipartite Graphs

S?o Paulo, SP - Brazil November 10-November 12

DOI Bookmark:

http://doi.ieeecomputersociety.org/10.1109/CAHPC.2003.1250335

15th Symposium on Computer Architectu ...

	This Article
	PURCHASE ARTICLE: $19 PDF HTML IEEE Xplore Subscribers
	Share
	Email this Article to a friend
	Bibliographic References
	ASCII Text BibTex RefWorks Procite/RefMan/Endnote
	Add to:
	Digg Furl Spurl Blink Simpy Google Del.icio.us Y!MyWeb
	Search
	Similar Articles Articles by José Soares Articles by Marco Stefanes

	ASCII Text	x
	José Soares, Marco Stefanes, "BSP/CGM Algorithm for Maximum Matching in Convex Bipartite Graphs," Computer Architecture and High Performance Computing, Symposium on, pp. 167, 15th Symposium on Computer Architecture and High Performance Computing (SBAC-PAD'03), 2003.

	BibTex	x
	@article{ 10.1109/CAHPC.2003.1250335, author = {José Soares and Marco Stefanes}, title = {BSP/CGM Algorithm for Maximum Matching in Convex Bipartite Graphs}, journal ={Computer Architecture and High Performance Computing, Symposium on}, volume = {0}, year = {2003}, isbn = {0-7695-2046-4}, pages = {167}, doi = {http://doi.ieeecomputersociety.org/10.1109/CAHPC.2003.1250335}, publisher = {IEEE Computer Society}, address = {Los Alamitos, CA, USA}, }

	RefWorks Procite/RefMan/Endnote	x
	TY - CONF JO - Computer Architecture and High Performance Computing, Symposium on TI - BSP/CGM Algorithm for Maximum Matching in Convex Bipartite Graphs SN - 0-7695-2046-4 SP EP A1 - José Soares, A1 - Marco Stefanes, PY - 2003 KW - null VL - 0 JA - Computer Architecture and High Performance Computing, Symposium on ER -

José Soares, Universidade de São Paulo

Marco Stefanes, Iniversidade Federal de Mato Grosso do Sul

Abipartite graph G = (V, W, E) is convex if there exists an ordering of the vertices of W such that, for each v ∈ V, the neighbors of v are consecutive in W. In this work we describe a BSP/CGM algorithm for finding a maximum matching in a convex bipartite graph. for p processors, the algorithm runs in time 0((|V|/p) lg(|V|/p) lg p) and it uses 0(lg p) communication rounds.

Citation:

José Soares, Marco Stefanes, "BSP/CGM Algorithm for Maximum Matching in Convex Bipartite Graphs," sbac-pad, pp.167, 15th Symposium on Computer Architecture and High Performance Computing (SBAC-PAD'03), 2003

Peer Review Notice | Give Us Feedback

Usage of this product signifies your acceptance of the Terms of Use.