An Optimal Algorithm For Reducing Edge-Solvable Mutual Exclusion Graphs

A mutual exclusion graph can be used to model a graphical mutual exclusion problem where a concurrent process is represented by a vertex and a mutual exclusion constraint between two processes is represented by an edge joining the two corresponding vertices. The first step of an algorithm for generating very efficient semaphore-based edge-solvable synchronization solutions for a class of graphical mutual exclusion problems calls for reducing the mutual exclusion graph to an optimal final graph with a single composite vertex representing them. The process of reduction involves the identification of similar vertices (with identical neighbors except, perhaps, the vertices themselves) and the replacement of the similar vertices by a composite vertex. In this paper, a fast worst case O(N2) reduction algorithm, where N is the number of vertices in the graph, that adds vertices incrementally to build the final graph is presented. Using the new algorithm, the entire algorithm for the automatic generation of edge-solvable solutions becomes O(N2) too. Because of the vast improvement over the straightforward O(N4) reduction algorithm, this algorithm should also be of theoretical interest. Since the number of edges is O(N2), and every edge must be visited in any graph reduction algorithm, the algorithm is optimal.