Optimizing concurrency under Scheduling by Edge Reversal
Carlos E. Marciano, Gladstone M. Arantes, Abílio Lucena, Luidi Gelabert Simonetti, Luérbio Faria, Felipe M. G. França · Networks · 2020
Abstract Scheduling by Edge Reversal provides an order of operation for nodes in a graph, but maximizing or minimizing the resulting concurrency is hard. In this paper, we discuss a series of real‐world applications for this technique and propose algorithms for both problems. For maximum concurrency, we prove its general inapproximability and introduce approximation algorithms for classes of graphs. For minimum concurrency, we use hardness and inapproximability results to establish its relation to longest cycles, while also introducing a novel application for assembling musical phrases.