Pytania otagowane jako hamiltonian-paths

2
Hamiltoniczność wykresów k-regularnych
Wiadomo, że NP-kompletne jest sprawdzenie, czy cykl hamiltonowski istnieje na 3-regularnym wykresie, nawet jeśli jest on płaski (Garey, Johnson i Tarjan, SIAM J. Comput. 1976) lub dwustronny (Akiyama, Nishizeki, i Saito, J. Inform. Proc. 1980) lub w celu przetestowania, czy cykl hamiltonowski istnieje na wykresie 4-regularnym, nawet jeśli jest to …
1
Chcę, aby prosty gadżet udowodnił, że cyklarny plan Hamiltonian NP-Complete (od cyklu Hamiltonian)
Wiadomo, że cykl hamiltonowski (w skrócie szynka) jest zakończony NP, a cykl szynki Planar jest zakończony NP. Dowód na cykl szynkowy nie pochodzi z cyklu szynkowego. Czy jest fajny gadżet, który, biorąc pod uwagę wykres G, zastąpi wszystkie skrzyżowania jakimś płaskim gadżetem, dzięki czemu masz płaski wykres G 'taki, że …
1
Czy najdłuższy problem szlaku jest łatwiejszy niż problem najdłuższej ścieżki?
Najdłuższy problem ze ścieżką to trudność NP. (Typowy?) Dowód polega na zmniejszeniu problemu ścieżki hamiltonowskiej (która jest NP-zupełna). Zauważ, że tutaj ścieżka jest uważana za (węzłową) prostą. Oznacza to, że żaden wierzchołek nie może wystąpić więcej niż jeden raz na ścieżce. Oczywiście jest to również proste dla krawędzi (żadna krawędź …
3
Klasy wykresów z łatwym cyklem hamiltonowskim, ale z TSP NP-twardym
Hamiltona Cykl Problem (HC) polega na znalezieniu cykl, który przechodzi przez wszystkie wierzchołki w danym undirected wykresu. Problem komiwojażera (TSP), polega na znalezieniu się cykl, który przechodzi przez wszystkie wierzchołki w danej krawędzi wykresu ważonych minimalizuje całkowitą odległość, mierzoną przez sumę mas krawędzi w cyklu. HC jest szczególnym przypadkiem TSP …
4
Lista problemów silnie NP-trudnych z danymi liczbowymi
Szukam silnie trudnych NP problemów dla redukcji. Do tej pory znalazłem następujące problemy: Problem z 3 partycjami problem z pakowaniem pojemników Trójwymiarowe dopasowanie numeryczne TSP Każdy problem NP-zupełny bez danych liczbowych, np. SATYSFIABILNOŚĆ, CYKL HAMILTONII, 3-KOLOURABILNOŚĆ. Czy ktoś zna listę problemów o wysokim stopniu NP? Jeśli nie, zbudujmy tutaj. Czy …
1
Jaka jest oczekiwana długość najkrótszej ścieżki hamiltonowskiej w losowo wybranych punktach z siatki planarnej?
kkk różnych punktów wybiera się losowo z siatki . (Oczywiście i jest daną stałą liczbą.) Na podstawie tych punktów budowany jest kompletny wykres ważony, tak że ciężar krawędzi między wierzchołkiem a wierzchołkiem jest równy odległości Manhattanu dwóch wierzchołków na pierwotnej siatce .p × qp×qp\times qk ≤ p × qk≤p×qk\leq p\times …
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.