Document Type
Technical Report
Publication Date
2015-11-20
DOI:
10.7936/K747486D
Technical Report Number
WUCSE-2015-006
Abstract
Let G=(V,E) be an undirected graph with n vertices and m edges, in which each vertex u is assigned an integer priority in [1,n], with 1 being the ``highest'' priority. Let M be a matching of G. We define the priority score of M to be an n-ary integer in which the i-th most-significant digit is the number of vertices with priority i that are incident to an edge in M. We describe a variation of the augmenting path method (Edmonds' algorithm) that finds a matching with maximum priority score in O(mn) time.
Recommended Citation
Turner, Jonathan, "Maximum Priority Matchings" Report Number: WUCSE-2015-006 (2015). All Computer Science and Engineering Research.
https://openscholarship.wustl.edu/cse_research/509
Comments
Permanent URL: http://dx.doi.org/10.7936/K747486D