Research Article
On the Computational Complexity of Software (Re)Modularization: Elaborations and Opportunities
@ARTICLE{10.4108/eai.3-12-2015.2262449, author={Todd Wareham}, title={On the Computational Complexity of Software (Re)Modularization: Elaborations and Opportunities}, journal={EAI Endorsed Transactions on Self-Adaptive Systems}, volume={2}, number={7}, publisher={ACM}, journal_a={SAS}, year={2016}, month={5}, keywords={software (re)modularization, computational complexity, parameterized computational complexity}, doi={10.4108/eai.3-12-2015.2262449} }- Todd Wareham
Year: 2016
On the Computational Complexity of Software (Re)Modularization: Elaborations and Opportunities
SAS
EAI
DOI: 10.4108/eai.3-12-2015.2262449
Abstract
Software system modularization and remodularization are key challenges in software engineering. All previous research has assumed that these problems are computationally intractable and hence focused on heuristic methods such as
hill-climbing, evolutionary algorithms, and simulated annealing that are fast but do not guarantee to produce solutions of optimal or even near-optimal quality. However, this intractability has never been formally established. In this paper, we give the first proofs of the $NP$-hardness of software modularization and remodularization relative to several models of module-internal connectivity. We
also review three popular algorithmic approaches for producing provably optimal or near-optimal solutions efficiently and both discuss the applicability of these approaches in and list results in the literature relevant to
practical software modularization and remodularization.
Copyright © 2015 T. Wareham, licensed to EAI. This is an open access article distributed under the terms of the Creative Commons Attribution licence (http://creativecommons.org/licenses/by/3.0/), which permits unlimited use, distribution and reproduction in any medium so long as the original work is properly cited.