Abstract
The min k-cut problem is an NP-hard generalization of the min-cut problem. The problem consists in separating a weighted graph with k specified vertices into k subgraphs, such that the total weight between subgraphs is minimized. This problem has important applications in computer science, engineering, and management science. In this article the author develops a hybrid genetic algorithm, a mimetic algorithm, by combining the genetic algorithm, which uses variable-length chromosomes, a max-flow/min-cut based greedy heuristics method, and part of the Tabu search approach to solve the min k-cut problem. Preliminary computational experiments demonstrate the efficiency and performance of the proposed mimetic algorithm.