An efficient algorithm to find the maximum matching on trapezoid graphs

Abstract. The computation of maximum matching is an important task in graph theory. For general graph an O( n.m) time algorithm is available to solve this problem. In this paper, an efficient algorithm is presented which takes O(n2) time and O(n+m) space for a trapezoid graph, where n and m represent the number of vertices and the number of edges of the graph. 1