1 The Partitioning Problem
Graph partitioning is a fundamental problem for many scientists. This problem arises in many graphs applications and consists in dividing the vertices into several sets of roughly equal “size” in such a way that the weight of edges between sets is as small as possible. A classical application of graph partitioning is parallel computing, to reduce the communication between processors. But applications of graph partitioning include also VLSI design, data clustering, image segmentation, and mesh partitioning of a 2D surface of an airfoil. A new partitioning problem consists of a new organization of the European airspace. This is the Functional Airspace Block Optimized Process (FABOP) project. We will see more precisely this subject in section 5.