Please use this identifier to cite or link to this item:
|Scopus||Web of Science®||Altmetric|
|Title:||Computing minimum cuts by randomized search heuristics|
|Citation:||Proceedings of the 10th Annual Conference on Genetic and Evolutionary Computation, 2008: pp. 779-786|
|Publisher Place:||New York|
|Conference Name:||Genetic and Evolutionary Computation Conference (10th : 2008 : Atlanta, Georgia)|
|Frank Neumann, Joachim Reichel and Martin Skutella|
|Abstract:||We study the minimum s-t-cut problem in graphs with costs on the edges in the context of evolutionary algorithms. Minimum cut problems belong to the class of basic network optimization problems that occur as crucial subproblems in many real-world optimization problems and have a variety of applications in several different areas. We prove that there exist instances of the minimum s-t-cut problem that cannot be solved by standard single-objective evolutionary algorithms in reasonable time. On the other hand, we develop a bi-criteria approach based on the famous maximum-flow minimum-cut theorem that enables evolutionary algorithms to find an optimum solution in expected polynomial time.|
|Rights:||ACM New York, NY, USA ©2008|
|Appears in Collections:||Computer Science publications|
Files in This Item:
There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.