Authors: Frank Neumann Joachim Reichel Martin Skutella
Publish Date: 2009/11/17
Volume: 59, Issue: 3, Pages: 323-342
Abstract
We study the minimum stcut 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 realworld optimization problems and have a variety of applications in several different areas We prove that there exist instances of the minimum stcut problem that cannot be solved by standard singleobjective evolutionary algorithms in reasonable time On the other hand we develop a bicriteria approach based on the famous maximumflow minimumcut theorem that enables evolutionary algorithms to find an optimal solution in expected polynomial timeThis article is published under an open access license Please check the Copyright Information section for details of this license and what reuse is permitted If your intended use exceeds what is permitted by the license or if you are unable to locate the licence and reuse information please contact the Rights and Permissions team
Keywords: