The edge expansion is an NP-hard to compute graph constant and gives us information about the connectivity of a graph. It is the minimum ratio of the number of edges joining two sets and the size of the smaller set over all possible non-trivial bipartitions of the vertices. The edge expansion of a connected graph is small if there is a bottleneck between two large parts of the graph. Because of this fact, it is for example used in clustering or network design. There are some heuristics to find a bipartition, like the well-known spectral clustering. This fractional optimization problem does not fit into the typical setting like other graph constants as the maximum cut which are NP-hard to compute. We propose different strategies to compute the edge expansion efficiently. One is to divide the problem into subproblems of an easier-to-handle type. Another one is to apply Dinkelbach's algorithm for fractional programming. Furthermore, we investigate the conjecture of Mihail and Vazirani, stating that the edge epxansion of the graph from a 0/1-polytope is at least 1, using our techniques.

Zum Vortrag: „Von der Konfrontation zur Kooperation – Brücken bauen anstatt Mauern aufstellen“> Einführung in die kooperative und konstruktive Konfliktbearbeitung im schulischen Feld> Konflikttheoretische Ansätze mit Bezug zur praktischen Umsetzung in der Schule> Schulmediation – Mediation in der Schule im engeren und im weiteren Sinne> Begriffsklärungen und Abgrenzungen zu weiteren Beratungsformaten> Ansprechpersonen unterschiedlicher Fachrichtungen im schulischen Kontext