Springe direkt zu Inhalt

Daniel Yu:

Removing popular faces with additional curves

Kurzbeschreibung

In dieser Arbeit untersuchen wir das Problem, populäre Flächen mithilfe des Hinzufügen von Kurven zu behandeln. De Nooijer, Terziadis, Weinberger, Masárová, Mchedlidze, Löffler and Rote haben gezeigt, dass dieses Problem NP-schwer ist, sich jedoch unter bestimmten Parametern randomisiert in polynomieller Zeit lösen lässt. Dieser Ansatz basiert auf einer Reduktion auf das Problem, ob ein Polynom das Nullpolynom ist, wobei die Entscheidung durch zufällige Auswertung des Polynoms über einem geeigneten Körper getroffen wird.

Wir implementieren die Ideen und testen diesen Ansatz auf synthetisch generierte Graphen. Unsere empirischen Auswertungen zeigen, dass die Fehlerwahrscheinlichkeiten weit niedriger sind als die theoretischen Obergrenzen und diese weiter minimiert werden können.

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