Wenn wir davon ausgehen, daß die weit verbreitete Annahme P≠NP gilt, so können viele wichtige Probleme nicht in polynomieller Zeit gelöst werden. Allerdings gibt es verschiedene Ansätze, dennoch exakte Lösungen für solche Probleme zu berechnen. Besonders hervorzuheben sind hier die Algorithmen mit moderater exponentieller Laufzeit und Algorithmen aus dem Gebiet der parametrisierten Komplexität. In diesem Projekt untersuchten wir möglichst intuitive Algorithmen, welche in der Regel aus einem der beiden oben genannten Gebieten stammen. Die Grundeigenschaft von intuitiven Algorithmen ist dabei, daß sie einer einfachen Grundidee folgen sollen und möglichst wenig Overhead enthalten sollen. Gleichzeitig sollen sie aber Probleme in relativ geringer Zeit exakt lösen. Die geforderte Einfachheit ist bei letzterem Aspekt natürlich ein Nachteil, zumindest wenn wir Algorithmen in Bezug auf ihre theoretischen Schranken hin analysieren. Dies muss meist durch eine deutlich aufwendigere Analyse ausgeglichen werden. So mußten wir zum Beispiel die Measure&Conquer Methode auf parametrisierte Probleme anpassen oder aber einen computerunterstützten Beweis zur Hilfe ziehen. Allerdings gibt es mehrere Aspekte von intuitiven Algorithmen, die diesen Nachteil ausgleichen. Zum einen ist die Laufzeit von intuitiven Algorithmen, sei sie im Allgemeinen auch höher als die von komplizierteren Algorithmen, zumindest auf kleinen Instanzen oft konkurrenzfähig. Auf größeren Instanzen übersteigt aber auch die Laufzeit von komplizierteren Algorithmen jegliche sinnvollen Werte, so daß intuitive Algorithmen in den meisten relevanten Fällen dennoch zu bevorzugen sind. Zudem lassen sich intuitive Algorithmen oft deutlich leichter implementieren, da in theoretischen Algorithmen oft sehr komplexe Operationen versteckt sind. Schließlich sind intuitive Algorithmen aber auch ästhetisch zu bevorzugen. Komplizierte Algorithmen sind oft nur deshalb kompliziert, um ihre theoretische Analyse zu vereinfachen oder erst zu ermöglichen. Die zusätzliche Komplexität verrät uns daher oft nur, daß unsere Analysewerkzeuge unzureichend sind, und liefert uns wenig Information darüber, worin die Schwierigkeit des Problems selbst liegt. Oft gelang es uns aber im Rahmen des Projekts sogar, intuitive Algorithmen zu entwickeln, die herkömmlichen Algorithmen auch in Hinsicht auf eine traditionelle Worst-Case Analyse überlegen sind. Unter anderem untersuchten wir im Rahmen des Projektes die folgenden Probleme: - Basierend auf oberen Schranken für die Baumweite von Graphen, fanden wir Algorithmen für Max-2-SAT und MaxCut mit einer Laufzeit von O*(1.128m). Hierbei bezeichnet m die Anzahl der Klauseln der Formel bzw. die Anzahl der Kanten eines Graphen. - Im Falle von Maximum Leaf Spanning Tree, konstruierten wir einen parametrisierten Algorithmus mit einer Laufzeit von O*(4k), der nicht auf ungerichteten, sondern auch auf gerichteten Graphen eine Lösung findet. - Für Partial Vertex Cover entwarfen wir einen intuitiven Algorithmus, dessen Laufzeit durch O*(1.396t) beschränkt ist. Außerdem entwickeln wir einen auf diesem Algorithmus basierenden randomisierten Algorithmus mit einer Laufzeit von O*(1.2993t). - Weiterhin zeigten wir, daß Partial Dominating Set mit einer Laufzeit von von O*(4 + εt) gelöst werden kann. - Für das Irredundant Set Problem konnten wir mittels eines intuitiven Algorithmus als erste die triviale Schranke von O*(2|V|) verbessern. - Schließlich entwarfen wir einen intuitiven Algorithmus für Independent Set mit einer Laufzeit von O*(1.2132|V|).