Springe direkt zu Inhalt

Sebastian Feist:

Max-Cut on Planar Graphs

Kurzbeschreibung

Finding a maximum cut on general graphs is a well known NP-hard problem. However, if we are willing to limit ourselves to the class of planar graphs, it is possible to solve the problem in polynomial time. In this thesis we will have a closer look at such a polynomial time algorithm by Liers and Pardella, and use an implementation of it to see how a basic approximation algorithm for general maximum cut performs in the planar case.

Abschluss
Bachelor of Science (B.Sc.)
Abgabedatum
27.02.2026