ISBN 9783843900201

978-3-8439-0020-1, Reihe Informatik

Gregor L. Pardella
Efficient Polynomial-Time Algorithms for Special Graph Partitioning Problems

188 Seiten, Dissertation Universität Köln (2011), Softcover, A5

Zusammenfassung / Abstract

In this thesis we study some interesting polynomial-time solvable optimization problems, motivated by those problems which arise while investigating ground-state properties of Ising spin glasses in different settings. We aim in designing new solution approaches, which we prove to work well in practice, and in improving the running time of known methods. We propose a new polynomial-time algorithm for solving the maximum cut problem on two-dimensional grid graphs. This approach is generalized to be applicable on arbitrary planar graphs and thus allows for any graph of interactions in the physics setting, given it is planar. Further, we show how to extend the latter approach with straightforward modifications to solve the problem of finding an optimum T-join in general graphs. These new approaches are more nifty and more practical than existing methods. The aforementioned problems are solved as matching problems on some auxiliary graphs. In theory, one can show that a divide-and-conquer approach proposed by Lipton and Tarjan in 1979 gives best asymptotic running-time bounds for the maximum weight matching problem on planar graphs. However, neither are practical experiments reported nor is an implementation available. Hence, we evaluate the divide-and-conquer approach and present our computational results. It turns out that it is preferable to use modern algorithmic techniques, such as multiple augmenting path search trees or good initial solutions, rather than the divide-and-conquer method. Besides the physics application, we address the problem of assigning layers to net segments in the VLSI chip design process. We restrict ourselves to the two-layer assignment problem which can be solved by a transformation to a planar maximum cut problem. We use our new planar maximum cut algorithm as a backbone for this problem and show that it is possible to achieve very good results on representative real-world chips while respecting practical constraints. Moreover, we consider the problem of finding the ground-state of random field Ising magnets. It is well-known that this can be modelled as a minimum s-t cut or rather a maximum s-t flow problem on the graph of interactions. To improve the running time of existing solution approaches, we propose graph transformations which conserve optimum flow solutions but may reduce the graph size considerably. Finally, a new hybrid maximum s-t flow algorithm is discussed which is designed to work well in the physics setting.