Pytania otagowane jako treewidth

Pytania dotyczące szerokości wykresów. Grafy o małej szerokości drzewa dopuszczają szybkie algorytmy dziel i zwyciężaj dla wielu problemów grafowych, które są NP-trudne w przypadku grafów ogólnych.

5
Geneza pojęcia treewidth
Moje dzisiejsze pytanie jest (jak zwykle) trochę głupie; ale prosiłbym cię o pomyślne rozważenie. Chciałem wiedzieć o genezie i / lub motywacji leżącej u podstaw koncepcji treewidth. Z pewnością rozumiem, że jest on stosowany w algorytmach FPT, ale nie sądzę, że to był powód, dla którego zdefiniowano to pojęcie. Pisałem …
1
Hipoteza odbudowy i częściowe 2-drzewa
Przypuszczenie o rekonstrukcji mówi, że wykresy (z co najmniej trzema wierzchołkami) są określane jednoznacznie przez ich podgrupy usunięte z wierzchołków. Ta hipoteza ma pięć dekad. Przeszukując odpowiednią literaturę, odkryłem, że następujące klasy grafów są rekonstruowalne: drzewa wykresy odłączone, wykresy, których dopełnienie jest odłączone regularne wykresy Maksymalne wykresy zewnętrzne maksymalne wykresy …
1
Czy nadal jest możliwe określenie złożoności obliczania szerokości wykresów płaskich?
Dla stałej można określić w czasie liniowym, biorąc pod uwagę wykres wejściowy G , czy jego szerokość wynosi ≤ k . Jednakże, gdy zarówno k jak i G są podane jako dane wejściowe, problem jest trudny NP. ( Źródło ).k∈Nk∈Nk \in \mathbb{N}GGG≤k≤k\leq kkkkGGG Jednak gdy wykres wejściowy jest płaski , …
1
Algorytmy przestrzeni logów na wykresach z ograniczoną szerokością drzewa
Szerokość drzewa mierzy, jak blisko wykresu znajduje się drzewo. Trudno jest obliczyć szerokość drzewa. Najbardziej znany algorytm aproksymacyjny osiąga współczynnik .O ( log n----√)O(logn)O(\sqrt{{\log}n}) Twierdzenie Courcelle'a stwierdza, że dowolną właściwość grafów definiowalną w monadycznej logice drugiego rzędu (MSO2) można rozstrzygać w czasie liniowym na dowolnej klasie wykresów o ograniczonej szerokości …
1
Algorytmiczne zalety szerokości ścieżki w porównaniu do szerokości
Treewidth odgrywa ważną rolę w algorytmach FPT, częściowo dlatego, że wiele problemów jest FPT parametryzowanych przez treewidth. Powiązanym, bardziej ograniczonym pojęciem jest szerokość ścieżki. Jeśli wykres ma szerokość ścieżki , ma również szerokość co najwyżej , podczas gdy w kierunku przeciwnym, szerokość oznacza tylko szerokość ścieżki co najwyżej a to …
3
Co odróżnia łatwe globalne problemy od twardych globalnych problemów na wykresach ograniczonej szerokości?
Wiele trudnych problemów graficznych można rozwiązać w czasie wielomianowym na wykresach ograniczonej szerokości . Rzeczywiście, podręczniki zwykle używają np. Zestawu niezależnego jako przykładu, co jest problemem lokalnym . Z grubsza problem lokalny to problem, którego rozwiązanie można zweryfikować, badając niewielkie sąsiedztwo każdego wierzchołka. Co ciekawe, nawet problemy (takie jak ścieżka …
2
Rozwiązane w czasie wielomianowe wystąpienia Max-Sat
Problem Max-Sat prosi o znalezienie przypisania formuły CNF, która spełnia jak najwięcej klauzul. Dla prostszego problemu SAT istnieje wiele znanych specjalnych przypadków, które można rozwiązać w czasie wielomianowym, np. Możemy rozwiązać 2-SAT w czasie wielomianowym. W przypadku Max-Sat sytuacja jest inna, ponieważ Max-Sat jest trudny dla NP nawet dla formuł …
18 sat  treewidth  max2sat 
5
Algorytmy szybkiej prędkości
Chciałbym obliczyć szerokość wykresu. Istnieją naprawdę dobre heurystyki dla innych problemów związanych z grafem NP-twardym, takich jak VF2 dla izomorfizmu podgraficznego , z kodem dostępnym na przykład w igraph . Wypróbowałem je na moich wykresach i okazało się, że działają bardzo szybko dla moich danych. Czy są jakieś szybkie algorytmy …
2
Zakazane nieletnie dla ograniczonych wykresów szerokości
To pytanie jest podobne do jednego z moich poprzednich pytań. Wiadomo, że jest niedozwolonym pomniejszeniem dla wykresów szerokości co najwyżej .Kt+2Kt+2K_{t+2}ttt Czy istnieje ładnie skonstruowana, sparametryzowana, nieskończona rodzina wykresów (innych niż pełne wykresy i wykresy siatki), które są minimalnie zabronionymi nieletnimi dla wykresów o każdej szerokości. Innymi słowy, czy istnieje …
1
Zmniejszanie rozkładu drzewa o minimalnej szerokości w czasie wielomianowym
Jak dobrze wiadomo, rozkład drzewa wykresu składa się z drzewa ze skojarzoną torbą dla każdego wierzchołka , który spełnia następujące warunki:T T v ⊆ V ( G ) v ∈GGGTTTTv⊆V(G)Tv⊆V(G)T_v \subseteq V(G)v∈V(T)v∈V(T)v \in V(T) Każdy wierzchołek występuje w jakimś workiem .TGGGTTT Dla każdej krawędzi znajduje się worek zawierający oba punkty …
2
Czy jest jakiś problem w
ΣP2Σ2P\mathsf{\Sigma^P_2}PP\mathsf{P} na ograniczonych wykresach szerokości drzewa. W rzeczywistości myślę, że te problemy są trudniejsze niż użycie normalnego programowania dynamicznego na wykresach ograniczonej szerokości do ich rozwiązania.
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.