An Efficient Algorithm for Combining Verification and Validation Methods. Mendoza, I., Souza, U., Kalinowski, M., Interian, R., & Murta, L. In 45th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2019, Novy Smokovec, Slovakia, January 27-30, pages 324-340, 2019. Author version doi abstract bibtex 2 downloads An adequate combination of verification and validation (V&V) methods is important to improve software quality control throughout the development process and to reduce costs. However, to find an appropriate set of V&V methods that properly addresses the desired quality characteristics of a given project is a NP-hard problem. In this paper, we present a novel approach that combines V&V methods efficiently in order to properly cover a set of quality characteristics. We modelled the problem using a bipartite graph to represent the relationships between V&V methods and quality characteristics. Then we interpreted our problem as the Set Cover problem. Although Set Cover is considered hard to be solved, through the theoretical framework of Parameterized Complexity we propose an FPT-Algorithm (fixed-parameter tractable algorithm) that effectively solves the problem, considering the number of quality characteristics to be covered as a fixed parameter. We conclude that the proposed algorithm enables combining V&V methods in a scalable and efficient way, representing a valuable contribution to the community.
@inproceedings{MendozaSKIM19,
author = {Isela Mendoza and
Uéverton Souza and
Marcos Kalinowski and
Ruben Interian and
Leonardo Murta},
title = {An Efficient Algorithm for Combining Verification and Validation Methods},
abstract = {An adequate combination of verification and validation (V&V) methods is important to improve software quality control throughout the development process and to reduce costs. However, to find an appropriate set of V&V methods that properly addresses the desired quality characteristics of a given project is a NP-hard problem. In this paper, we present a novel approach that combines V&V methods efficiently in order to properly cover a set of quality characteristics. We modelled the problem using a bipartite graph to represent the relationships between V&V methods and quality characteristics. Then we interpreted our problem as the Set Cover problem. Although Set Cover is considered hard to be solved, through the theoretical framework of Parameterized Complexity we propose an FPT-Algorithm (fixed-parameter tractable algorithm) that effectively solves the problem, considering the number of quality characteristics to be covered as a fixed parameter. We conclude that the proposed algorithm enables combining V&V methods in a scalable and efficient way, representing a valuable contribution to the community.},
booktitle = {45th International Conference on Current Trends in Theory and Practice of Computer Science, {SOFSEM} 2019, Novy Smokovec, Slovakia, January 27-30},
pages = {324-340},
year = {2019},
urlAuthor_version = {http://www.inf.puc-rio.br/~kalinowski/publications/MendozaSKIM19.pdf},
doi = {10.1007/978-3-030-10801-4_26},
}
Downloads: 2
{"_id":"Mq9zwKmrubjF7EeQr","bibbaseid":"mendoza-souza-kalinowski-interian-murta-anefficientalgorithmforcombiningverificationandvalidationmethods-2019","downloads":2,"creationDate":"2019-01-24T18:43:32.098Z","title":"An Efficient Algorithm for Combining Verification and Validation Methods","author_short":["Mendoza, I.","Souza, U.","Kalinowski, M.","Interian, R.","Murta, L."],"year":2019,"bibtype":"inproceedings","biburl":"https://bibbase.org/f/2Gq6bNPQ845THHiMW/KalinowskiPapers.bib","bibdata":{"bibtype":"inproceedings","type":"inproceedings","author":[{"firstnames":["Isela"],"propositions":[],"lastnames":["Mendoza"],"suffixes":[]},{"firstnames":["Uéverton"],"propositions":[],"lastnames":["Souza"],"suffixes":[]},{"firstnames":["Marcos"],"propositions":[],"lastnames":["Kalinowski"],"suffixes":[]},{"firstnames":["Ruben"],"propositions":[],"lastnames":["Interian"],"suffixes":[]},{"firstnames":["Leonardo"],"propositions":[],"lastnames":["Murta"],"suffixes":[]}],"title":"An Efficient Algorithm for Combining Verification and Validation Methods","abstract":"An adequate combination of verification and validation (V&V) methods is important to improve software quality control throughout the development process and to reduce costs. However, to find an appropriate set of V&V methods that properly addresses the desired quality characteristics of a given project is a NP-hard problem. In this paper, we present a novel approach that combines V&V methods efficiently in order to properly cover a set of quality characteristics. We modelled the problem using a bipartite graph to represent the relationships between V&V methods and quality characteristics. Then we interpreted our problem as the Set Cover problem. Although Set Cover is considered hard to be solved, through the theoretical framework of Parameterized Complexity we propose an FPT-Algorithm (fixed-parameter tractable algorithm) that effectively solves the problem, considering the number of quality characteristics to be covered as a fixed parameter. We conclude that the proposed algorithm enables combining V&V methods in a scalable and efficient way, representing a valuable contribution to the community.","booktitle":"45th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2019, Novy Smokovec, Slovakia, January 27-30","pages":"324-340","year":"2019","urlauthor_version":"http://www.inf.puc-rio.br/~kalinowski/publications/MendozaSKIM19.pdf","doi":"10.1007/978-3-030-10801-4_26","bibtex":"@inproceedings{MendozaSKIM19,\r\n author = {Isela Mendoza and \r\n Uéverton Souza and\r\n\t\t\t Marcos Kalinowski and\r\n\t\t\t Ruben Interian and\r\n Leonardo Murta}, \r\n title = {An Efficient Algorithm for Combining Verification and Validation Methods},\r\n abstract = {An adequate combination of verification and validation (V&V) methods is important to improve software quality control throughout the development process and to reduce costs. However, to find an appropriate set of V&V methods that properly addresses the desired quality characteristics of a given project is a NP-hard problem. In this paper, we present a novel approach that combines V&V methods efficiently in order to properly cover a set of quality characteristics. We modelled the problem using a bipartite graph to represent the relationships between V&V methods and quality characteristics. Then we interpreted our problem as the Set Cover problem. Although Set Cover is considered hard to be solved, through the theoretical framework of Parameterized Complexity we propose an FPT-Algorithm (fixed-parameter tractable algorithm) that effectively solves the problem, considering the number of quality characteristics to be covered as a fixed parameter. We conclude that the proposed algorithm enables combining V&V methods in a scalable and efficient way, representing a valuable contribution to the community.},\r\n booktitle = {45th International Conference on Current Trends in Theory and Practice of Computer Science, {SOFSEM} 2019, Novy Smokovec, Slovakia, January 27-30},\r\n pages = {324-340},\r\n year = {2019},\r\n urlAuthor_version = {http://www.inf.puc-rio.br/~kalinowski/publications/MendozaSKIM19.pdf},\r\n doi = {10.1007/978-3-030-10801-4_26},\r\n}\r\n\r\n","author_short":["Mendoza, I.","Souza, U.","Kalinowski, M.","Interian, R.","Murta, L."],"key":"MendozaSKIM19","id":"MendozaSKIM19","bibbaseid":"mendoza-souza-kalinowski-interian-murta-anefficientalgorithmforcombiningverificationandvalidationmethods-2019","role":"author","urls":{"Author version":"http://www.inf.puc-rio.br/~kalinowski/publications/MendozaSKIM19.pdf"},"metadata":{"authorlinks":{"kalinowski, m":"https://www-di.inf.puc-rio.br/~kalinowski/publications.html"}},"downloads":2,"html":""},"search_terms":["efficient","algorithm","combining","verification","validation","methods","mendoza","souza","kalinowski","interian","murta"],"keywords":[],"authorIDs":["2QsG9mfJnwX6MTuoJ"],"dataSources":["JhEx5LqjNuowkDTYw","vp6ff9ZJkhXGDuh9E","fNxekpJ4iGWMdJryo","FPdHx2YNMWt6KHbaS","oL8GbjE74fizfjkxY","Wbj3iHa4hGsGjEGJE","q7rgFjFgwoTSGkm3G","aKfxcyv7C9p9ytdpG","9pAzChfPy53GguqQk","B8Jierr7smZsGa7Jb","tvqztEQv84agmtPEB","ZCce9uhx7vt9PXPrc","FGDKYBjH9upApdKoL"]}