Research Article
On the Computational Complexity of Software (Re)Modularization: Elaborations and Opportunities
@INPROCEEDINGS{10.4108/eai.3-12-2015.2262449, author={Todd Wareham}, title={On the Computational Complexity of Software (Re)Modularization: Elaborations and Opportunities}, proceedings={9th EAI International Conference on Bio-inspired Information and Communications Technologies (formerly BIONETICS)}, publisher={ACM}, proceedings_a={BICT}, 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
BICT
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.
