Given a weighted undirected graph, the equicut problem consistsof finding a partition of the vertex set into two subsets ofequal cardinality such that the sum of the weights of the edgesbelonging to the cut defined by the partition is minimized.The problem is NP-hard and has several practical applications.In recent years a number of algorithms based on metaheuristictechniques have been proposed.In this work we first present a survey of the algorithms fromthe literature, then we propose a new tabu search algorithmand compare it with the other heuristics through extensivecomputational experiments on severalclasses of graphs with up to 4,000 nodes and 320,000 edges.The results show that our approach easily determines theoptimal solution for small graphs and its average performancesare greatly superior to those of the other approximating algorithms.
Solution of Large Weighted Equicut Problems / Dell'Amico, Mauro; M., Trubian. - In: EUROPEAN JOURNAL OF OPERATIONAL RESEARCH. - ISSN 0377-2217. - STAMPA. - 106:(1998), pp. 500-521.
Solution of Large Weighted Equicut Problems
DELL'AMICO, Mauro;
1998
Abstract
Given a weighted undirected graph, the equicut problem consistsof finding a partition of the vertex set into two subsets ofequal cardinality such that the sum of the weights of the edgesbelonging to the cut defined by the partition is minimized.The problem is NP-hard and has several practical applications.In recent years a number of algorithms based on metaheuristictechniques have been proposed.In this work we first present a survey of the algorithms fromthe literature, then we propose a new tabu search algorithmand compare it with the other heuristics through extensivecomputational experiments on severalclasses of graphs with up to 4,000 nodes and 320,000 edges.The results show that our approach easily determines theoptimal solution for small graphs and its average performancesare greatly superior to those of the other approximating algorithms.Pubblicazioni consigliate
I metadati presenti in IRIS UNIMORE sono rilasciati con licenza Creative Commons CC0 1.0 Universal, mentre i file delle pubblicazioni sono rilasciati con licenza Attribuzione 4.0 Internazionale (CC BY 4.0), salvo diversa indicazione.
In caso di violazione di copyright, contattare Supporto Iris