Zeitkomplexität von Vertexabdeckung gegen Clique für Fixed K
-
29-09-2020 - |
Frage
Ich habe zwei Möglichkeiten, ein unabhängiges Set-Problem der festen Größe zu lösen $ K $ für Graph $ g= (V,E) $ :
- Vertex-Abdeckungsalgorithmus, der in
Wie kann ich feststellen, welcher eine geringere Zeitkomplexität hat?Ich bin nicht sehr gut mit Algorithmen für NP-komplette Probleme und $ o ^ * $ Notation.Würde diese Funktionen plotten?Ich denke, dass der VC-Algorithmus einen beliebigen Polynom
Lösung
für jeden festen
Das Plotten der Kurven ist nicht so hilfreich, da dies asymptotische Aussagen sind.
das heißt, wenn Sie interessiert sind, wenn Sie an teilnehmen $ V $ und $ k$ , dann ist Ihre beste Option, um empirisch zu überprüfen, welcher dieser Algorithmen schneller ist.Asymptotische Notation ist hier nicht hilfreich, da es konstante Faktoren verbirgt, und diese könnten einen großen Unterschied für konkrete Werte von $ V $ und $ k $ .
Andere Tipps
Vertexabdeckung ist fixierbarer Parameter.
Es gibt einen einfachen
Unter einigen Annahmen gibt es keinen Algorithmus für K Clip mit Laufzeit $ F (k) n ^ C $ .
Wenn Ihr Diagramm eine spezielle Struktur hat, können die Ergebnisse verbessert werden.