Carleton University
Technical Report TR-95-12
May 1995
An Improved Maximum Matching Algorithm in a Permutation Graph
Abstract
We present an O(n log2 n) time algorithm for computing a maximum matching in a per- mutation graph on n-vertices. Our results are based on the algorithm of [12] for a two processor scheduling problem of [2]. The algorithm of [12] runs in O(n + m) time, where n and m are the vertices and dependencies, respectively of the given graph. Through vector dominance and using computational geometry techniques we provide a novel and improved algorithm for maximum matching in permutation graphs. We establish that the problem has an O(n log2 n) solution. Furthermore, if the dependency graph of a scheduling problem is known to be a permutation graph, then we now have an improved two-processor scheduling algorithm (if the number of edges is (n log2 n)).