Constructive heuristic for the vertex bisection problem
Fuente:
Redalyc
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Artículo científico |
| Lenguaje: | en |
| Publicado: |
Universidad Nacional Autónoma de México
2020
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1876472778265198592 |
|---|---|
| author | Norberto Castillo-García |
| author_facet | Norberto Castillo-García |
| contents | Constructive heuristic for the vertex bisection problem Norberto Castillo-García Paula Hernández-Hernández Ingeniería Constructive algorithm Heuristic optimization Vertex Bisection Problem The Vertex Bisection Problem (VBP) consists in partitioning a generic graph into two equally– sized subgraphs and such that the number of vertices in with at least one adjacent vertex in is minimized. This problem is NP–hard with practical applications in the telecommunication industry. In this article we propose a new constructive algorithm for VBP based on the Greedy Randomized Adaptive Search Procedure (GRASP) methodology. We call our algorithm CVBP. We compare CVBP with a previously published GRASP–based constructive algorithm (LIT) in order to assess the performance of our algorithm in practice. The results of the experiment showed that CVBP outperformed LIT by 75.83 % in solution quality. The validation of the experimental evidence was performed by the well–known Wilcoxon Signed Rank Sum Test. The test found statistical significance for a confidence level of 99.99 %. Therefore, we consider that our constructive heuristic is a good alternative to stochastically solve the Vertex Bisection Problem. 2020 artículo científico 1665-6423 https://www.redalyc.org/articulo.oa?id=47471673005 https://www.redalyc.org/journal/474/47471673005/ https://www.redalyc.org/journal/474/47471673005/html/ https://www.redalyc.org/journal/474/47471673005/47471673005.epub https://www.redalyc.org/journal/474/47471673005/movil 10.14482/INDES.30.1.303.661 en http://www.redalyc.org/revista.oa?id=474 Journal of Applied Research and Technology application/pdf Universidad Nacional Autónoma de México Journal of Applied Research and Technology (México) Num.4 Vol.18 |
| format | Artículo científico |
| id | redalyc_47471673005 |
| institution | Redalyc |
| language | en |
| publishDate | 2020 |
| publisher | Universidad Nacional Autónoma de México |
| spellingShingle | Constructive heuristic for the vertex bisection problem Norberto Castillo-García Ingeniería Constructive algorithm Heuristic optimization Vertex Bisection Problem Constructive heuristic for the vertex bisection problem Norberto Castillo-García Paula Hernández-Hernández Ingeniería Constructive algorithm Heuristic optimization Vertex Bisection Problem The Vertex Bisection Problem (VBP) consists in partitioning a generic graph into two equally– sized subgraphs and such that the number of vertices in with at least one adjacent vertex in is minimized. This problem is NP–hard with practical applications in the telecommunication industry. In this article we propose a new constructive algorithm for VBP based on the Greedy Randomized Adaptive Search Procedure (GRASP) methodology. We call our algorithm CVBP. We compare CVBP with a previously published GRASP–based constructive algorithm (LIT) in order to assess the performance of our algorithm in practice. The results of the experiment showed that CVBP outperformed LIT by 75.83 % in solution quality. The validation of the experimental evidence was performed by the well–known Wilcoxon Signed Rank Sum Test. The test found statistical significance for a confidence level of 99.99 %. Therefore, we consider that our constructive heuristic is a good alternative to stochastically solve the Vertex Bisection Problem. 2020 artículo científico 1665-6423 https://www.redalyc.org/articulo.oa?id=47471673005 https://www.redalyc.org/journal/474/47471673005/ https://www.redalyc.org/journal/474/47471673005/html/ https://www.redalyc.org/journal/474/47471673005/47471673005.epub https://www.redalyc.org/journal/474/47471673005/movil 10.14482/INDES.30.1.303.661 en http://www.redalyc.org/revista.oa?id=474 Journal of Applied Research and Technology application/pdf Universidad Nacional Autónoma de México Journal of Applied Research and Technology (México) Num.4 Vol.18 |
| title | Constructive heuristic for the vertex bisection problem |
| topic | Ingeniería Constructive algorithm Heuristic optimization Vertex Bisection Problem |
| url | https://www.redalyc.org/articulo.oa?id=47471673005 https://www.redalyc.org/journal/474/47471673005/ https://www.redalyc.org/journal/474/47471673005/html/ https://www.redalyc.org/journal/474/47471673005/47471673005.epub https://www.redalyc.org/journal/474/47471673005/movil |