Please use this identifier to cite or link to this item:
Scopus Web of Science® Altmetric
Type: Conference paper
Title: Computing minimum cuts by randomized search heuristics
Author: Neumann, F.
Reichel, J.
Skutella, M.
Citation: Proceedings of the 10th Annual Conference on Genetic and Evolutionary Computation, 2008: pp. 779-786
Publisher: ACM Press
Publisher Place: New York
Issue Date: 2008
ISBN: 9781605581309
Conference Name: Genetic and Evolutionary Computation Conference (10th : 2008 : Atlanta, Georgia)
Statement of
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
RMID: 0020107095
DOI: 10.1145/1389095.1389250
Published version:
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.