Constructive heuristic for the vertex bisection problem
Abstract: The Vertex Bisection Problem (VBP) consists in partitioning a generic graph into two equally-sized subgraphs A and B such that the number of vertices in A with at least one adjacent vertex in B 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.
| Main Authors: | , |
|---|---|
| Format: | Digital revista |
| Language: | English |
| Published: |
Universidad Nacional Autónoma de México, Instituto de Ciencias Aplicadas y Tecnología
2020
|
| Online Access: | http://www.scielo.org.mx/scielo.php?script=sci_arttext&pid=S1665-64232020000400187 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|