An Optimal Algorithm For Reducing Edge-Solvable Mutual Exclusion Graphs

Simple item page
dc.contributor.authorYue, Kwok-Bun
dc.date.accessioned2019-10-04T19:50:55Z
dc.date.available2019-10-04T19:50:55Z
dc.date.issued1994
dc.description.abstractA 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.en_US
dc.identifier.citationYue, K., An Optimal Algorithm For Reducing Edge-Solvable Mutual Exclusion Graphs. The Computer Journal. vol.37, no.2, pp129-138, 1994.en_US
dc.identifier.urihttps://hdl.handle.net/10657.1/1503
dc.publisherThe Computer Journalen_US
dc.titleAn Optimal Algorithm For Reducing Edge-Solvable Mutual Exclusion Graphsen_US
dc.typeArticleen_US

Files

Original bundle

Now showing 1 - 1 of 1
Thumbnail Image
Name:
optimalalgorithim.pdf
Size:
5.04 KB
Format:
Adobe Portable Document Format
Description:
Abstract and Citation
Download

License bundle

Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
1.71 KB
Format:
Item-specific license agreed upon to submission
Description:
Download

Collections

Kwok-Bun Yue
College of Science and Engineering