sas 16(7): e4

Research Article

On the Computational Complexity of Software (Re)Modularization: Elaborations and Opportunities

Download780 downloads
  • @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
Todd Wareham1,*
  • 1: Memorial University of Newfoundland
*Contact email: htwareham@gmail.com

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.