Title :
Parallel matching on expanders
Author :
Spencer, Thomas H.
Author_Institution :
Dept. of Math. & Comput. Sci., Nebraska Univ., Omaha, NE, USA
Abstract :
If a matching on a bipartite expander does not have maximum cardinality, it has a short augmenting path. This fact leads to an improved parallel algorithm for finding maximum cardinality matchings on such graphs. This paper describes a deterministic parallel algorithm paths that runs in (logn)4log log n+O(1) time on an EREW PRAM with O(nm) processors and that finds a maximum cardinality matching on an expander, n is the number of vertices of the graph and m is the number of edges of the graph
Keywords :
computational complexity; parallel algorithms; random-access storage; EREW PRAM; expanders; maximum cardinality; parallel algorithm; parallel matching; Bipartite graph; Computer science; Graph theory; Mathematics; Phase change random access memory; Routing;
Conference_Titel :
Parallel and Distributed Processing, 1991. Proceedings of the Third IEEE Symposium on
Conference_Location :
Dallas, TX
Print_ISBN :
0-8186-2310-1
DOI :
10.1109/SPDP.1991.218187
