caa a22 4500 445804807 CHVBK 20180317145153.0 cr unu---uuuuu 170323e20110301xx s 000 0 eng 10.1007/s00453-009-9370-8 doi (NATIONALLICENCE)springer-10.1007/s00453-009-9370-8 Computing Minimum Cuts by Randomized Search Heuristics [Elektronische Daten] [Frank Neumann, Joachim Reichel, Martin Skutella] 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 optimal solution in expected polynomial time. The Author(s), 2009 Evolutionary algorithms nationallicence Minimum s - t -cuts nationallicence Multi-objective optimization nationallicence Randomized search heuristics nationallicence Neumann Frank Algorithms and Complexity, Max-Planck-Institut für Informatik, Saarbrücken, Germany aut Reichel Joachim Institut für Mathematik, Technische Universität Berlin, Berlin, Germany aut Skutella Martin Institut für Mathematik, Technische Universität Berlin, Berlin, Germany aut Algorithmica Springer-Verlag 59/3(2011-03-01), 323-342 0178-4617 59:3<323 2011 59 453 https://doi.org/10.1007/s00453-009-9370-8 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00453-009-9370-8 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Neumann Frank Algorithms and Complexity, Max-Planck-Institut für Informatik, Saarbrücken, Germany aut NATIONALLICENCE 700 1- Reichel Joachim Institut für Mathematik, Technische Universität Berlin, Berlin, Germany aut NATIONALLICENCE 700 1- Skutella Martin Institut für Mathematik, Technische Universität Berlin, Berlin, Germany aut NATIONALLICENCE 773 0- Algorithmica Springer-Verlag 59/3(2011-03-01), 323-342 0178-4617 59:3<323 2011 59 453 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer