Paper Info
Title
A sublinear parallel algorithm for stable matching
Abstract
A parallel algorithm for the stable matching problem is presented. The algorithm is based on the primal-dual interior path-following method for linear programming. The main result is that a stable matching can be found in 0*(Jiii) time by a polynomial number of processors, where nz is the total length of preference lists of individuals. @ 2000 Published by Elsevier Sciencc B.V. All rights reserved.
Year
DOI
Venue
2000
10.1016/S0304-3975(99)00125-5
Theoretical Computer Science
Keywords
Field
DocType
Linear programming,sublinear parallel algorithm,stable matching,Non-expansive circuits,Stable matching
Sublinear function,Edit distance,Combinatorics,Stable marriage problem,Polynomial,Parallel algorithm,Linear programming,3-dimensional matching,Mathematics
Journal
Volume
Issue
ISSN
233
1-2
Theoretical Computer Science
ISBN
Citations 
PageRank 
0-89871-329-3
9
1.88
References 
Authors
5
3
Name
Order
Citations
PageRank
Tomás Feder11959184.99
Nimrod Megiddo24244668.46
Serge Plotkin32139281.56