Premium
Optimizing concurrency under Scheduling by Edge Reversal
Author(s) -
Marciano Carlos E.,
Arantes Gladstone M.,
Lucena Abilio,
Simonetti Luidi G.,
Faria Luerbio,
França Felipe M. G.
Publication year - 2021
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.22014
Subject(s) - concurrency , computer science , scheduling (production processes) , algorithm , theoretical computer science , mathematical optimization , distributed computing , mathematics
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.