Betrachten Sie das folgende Problem.
Gegeben: Ein vollständiges Diagramm mit echten nicht negativen Gewichten an den Kanten.
Aufgabe: Finden Sie einen planaren Teilgraphen mit maximalem Gewicht. ("Maximum" unter allen möglichen planaren Teilgraphen.)
Hinweis: Der Subgraph mit maximaler Gewichtung ist eine Triangulation. Wenn sich der vollständige Graph auf Eckpunkten befindet, hat er Kanten.
Frage: Was ist der beste verfügbare Algorithmus für dieses Problem? Was ist seine zeitliche Komplexität?
Dies ist selbst für gewichtete vollständige Diagramme NP-hart. Für einen einfachen Algorithmus können Sie einen Spanning Tree mit maximaler Gewichtung berechnen: Negieren Sie die Kantengewichte und führen Sie den Kruskal-Algorithmus aus. Dies ergibt ein Leistungsverhältnis von 1/3 (ein Spanning Tree hat Kanten, und wie Sie bemerken, kann ein maximaler planarer Teilgraph höchstens Kanten enthalten). Soweit ich weiß, wurde der Algorithmus in [1], der ein Leistungsverhältnis von mindestens 25/72 und höchstens 5/12 aufweist, nicht wesentlich verbessert (siehe jedoch, welche neueren Veröffentlichungen darauf verweisen).
Für vollständige Graphen, deren Kantengewichte der Dreiecksungleichung entsprechen, beträgt das Leistungsverhältnis des Algorithmus in [1] mindestens 3/8. Ich denke, der Algorithmus ist ziemlich kompliziert und kann in allgemeinen Graphen in -Zeit ausgeführt werden. Es gibt einige einfachere Varianten, die die Autoren ebenfalls mit unterschiedlichen Leistungsverhältnissen und möglicherweise besseren Laufzeiten präsentieren.