Longest Path Approximation Algorithmus von einem bestimmten Knoten

Ich suche nach einem Approximationsalgorithmus für das folgende Problem - Ich habe einen ungewichteten, ungerichteten Graphen mit Zyklen, und möchte den längsten Pfad beginnend von einem bestimmten Knoten finden. Ich bewerte Geschwindigkeit über Leistung (ein O (n^5) -Algorithmus wäre wahrscheinlich ein Overkill).Longest Path Approximation Algorithmus von einem bestimmten Knoten

Dies ist keine Hausaufgabe (ich schwöre!) Oder Arbeit verwandt, aber ich werde jeden Tipp schätzen, den Sie haben könnten.

Quelle

2010-02-08 r0u1i

ist dies für den Google-Wettbewerb? So bin ich gekommen, haha! – aramadia

Sie kennen mich auch gut :) – r0u1i

Ich bin für einen Approximationsalgorithmus für das folgende Problem suchen ...

Wissenschaftler für sie auch suchen. Sie haben auch proved, dass polynomische Konstanten-Faktor-Approximation nicht existiert, wenn P ≠ NP. Und die Zusammenfassung von this Artikel behauptet, dass es einen Approximationsalgorithmus für Ihr Problem enthält.

Quelle

2010-02-08 10:29:25

Wow, das wusste ich nicht. Ich dachte, dass das verallgemeinerte Problem einen konstanten Approximationsalgorithmus hat. Wie ist es, das Problem noch weiter zu begrenzen, indem man eine maximale Anzahl von Nachbarn hat, die konstant ist? – r0u1i

@ r0u1i, Whoops, der erste Artikel, den ich verlinkt habe, enthält auch einen Beweis, dass eine solche Einschränkung nicht hilft :-). –

Danke, Sie gewinnen :) – r0u1i

Longest Path Approximation Algorithmus von einem bestimmten Knoten

Antwort

Verwandte Themen