Faster Maximium Priority Matchings in Bipartite Graphs

Authors

Jonathan Turner, Washington University in St LouisFollow

Document Type

Technical Report

Publication Date

2015-12

Filename

WUCSE-2015-008.pdf

Technical Report Number

WUCSE-2015-008

Abstract

A maximum priority matching is a matching in an undirected graph that maximizes a priority score defined with respect to given vertex priorities. An earlier paper showed how to find maximum priority matchings in unweighted graphs. This paper describes an algorithm for bipartite graphs that is faster when the number of distinct priority classes is limited. For graphs with k distinct priority classes it runs in O(kmn1/2) time, where n is the number of vertices in the graph and m is the number of edges.

Comments

Permanent URL: http://dx.doi.org/10.7936/K7J101HP

Recommended Citation

Turner, Jonathan, "Faster Maximium Priority Matchings in Bipartite Graphs" Report Number: WUCSE-2015-008 (2015). All Computer Science and Engineering Research.
https://openscholarship.wustl.edu/cse_research/511