On the validity of a front-oriented approach to partitioning large sparse graphs with a connectivity constraint (Q1921328)

The authors present a heuristic which approximates the \(p\)-edge partitioning problem for large sparse graphs with a connectivity constraint on the subsets. It is decomposed into two parts: the computation of an initial partition and an iterative retrofitting process. For the initial step the finiteness and correctness is proven and it is showed by using front-based tools that its complexity grows at most linearly with the number of edges of the graph. For the retrofitting method again based on front techniques a new balancing step has been designed in order to reduce the number of iterations. To illustrate the quality and speed of the heuristic a few examples are given.