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.

1
Wyrażenia o szerokości kliki z głębokością logarytmiczną
Kiedy otrzymujemy rozkład drzewa wykresu o szerokości , istnieje kilka sposobów, dzięki którym możemy go uczynić „ładnym”. W szczególności wiadomo, że można go przekształcić w rozkład drzewa, w którym drzewo jest binarne, a jego wysokość wynosi . Można to osiągnąć przy zachowaniu szerokości rozkładu co najwyżej . (Patrz np. „Algorytmy …
5
Dokładne algorytmy dla zestawu R-Dominującego na wykresach ograniczonej Treewidth
Biorąc pod uwagę wykres, G=(V,E)G=(V,E)G = (V, E) , to znaleźć optymalną rrr -domination dla GGG . Oznacza to, że chce podzbiór SSS o VVV tak, że wszystkie wierzchołki GGG znajdują się w odległości co najwyżej rrr z pewnym wierzchołka w SSS , przy jednoczesnym zminimalizowaniu rozmiaru .SSS Z tego, …
2
Parametr wykresu prawdopodobnie związany z szerokością
Interesują mnie wykresy nnn wierzchołków, które można wytworzyć w następujący sposób. Zacznij od dowolnego wykresu GsolG na k≤nk≤nk\le n wierzchołków. Oznacz wszystkie wierzchołki w GsolG jako nieużywane . Opracowanie nowego wykres dodaje się nowy wierzchołek V , który jest połączony z jedną lub więcej niewykorzystanych wierzchołków G i nie jest …
1
Czy istnieją ciekawe klasy grafów, w których obliczanie szerokości jest trudne (łatwe)?
Treewith jest ważnym parametrem grafu, który wskazuje, jak blisko wykres jest od drzewa (choć nie w ścisłym sensie topologicznym). Powszechnie wiadomo, że obliczenie szerokości jest trudne dla NP. Czy są jakieś naturalne klasy wykresów, w których trudno jest obliczyć szerokość ? Podobnie: Czy istnieją ciekawe klasy grafów, w których obliczanie …
1
Jaka jest prawidłowa definicja drzewa
Jak mówi tytuł, jaka jest poprawna definicja drzewa ? Istnieje kilka artykułów, które mówią o drzewach K i drzewach częściowych K jako alternatywnych definicjach dla wykresów o ograniczonej szerokości i widziałem wiele z pozornie niepoprawnych definicji. Na przykład co najmniej jedno miejsce definiuje drzewa- K w następujący sposób:kkkkkkkkkkkk Wykres nazywa …
1
Czy szerokość sugeruje istnienie nieletniego ?
Niech zostanie naprawione, a będzie (połączonym) wykresem. Jeśli się nie mylę, z pracy Bodlaendera [1, Twierdzenie 3.11] wynika, że ​​jeśli szerokość wynosi w przybliżeniu co najmniej , wówczas zawiera gwiazdę jako pomniejszą.G G 2 k 3 G K 1 , kkkksolGGsolGG2 tys3)2k32k^3solGGK.1 , kK1,kK_{1,k} Czy możemy zmniejszyć termin ? To …
1
Typowa twardość rozkładu drzew?
Rozkład drzew jest trudny w najgorszym przypadku, ale chciwa metoda wydaje się być prawie optymalna w małych rzeczywistych sieciach. Czy coś wiadomo o twardości rozkładu drzewa „typowego” wystąpienia jakiejś klasy grafów? Czy istnieje przykład rodziny grafów, w której chciwe metody rozkładu drzew źle się sprawdzają?
2
Minimalna szerokość drzewa obwodu dla WIĘKSZOŚCI
Jaka jest minimalna szerokość drzewa obwodu powyżej {∧,∨,¬}{∧,∨,¬}\{\wedge,\vee,\neg\} do obliczenia MAJ? Tutaj MAJ :{0,1}n→{0,1}:{0,1}n→{0,1}:\{0,1\}^n \rightarrow \{0,1\} wyprowadza 1, jeśli co najmniej połowa jego danych wejściowych to 111 . Dbam tylko o rozmiar obwodu (powinien być wielomianowy) i że dane wejściowe powinny być odczytywane tylko raz, chociaż rozwarcie bramki wejściowej może …
2
Jaka jest korelacja między wysokością a twardością instancji dla losowego 3-SAT?
Ten ostatni artykuł z FOCS2013, Strong Backdoors to Bounded Treewidth SAT autorstwa Gaspersa i Szeidera mówi o związku między szerokością wykresu klauzuli SAT a twardością instancji. W przypadku losowych instancji 3-SAT, tj. Instancji losowo wybranych 3-SAT, jaka jest korelacja między szerokością wykresu klauzulowego a twardością instancji? „Twardość wystąpienia” może być …
1
Właściwości MSO, wykresy płaskie i niewielkie wykresy
Twierdzenie Courcelle'a stwierdza, że ​​każdą właściwość grafu definiowaną w monadycznej logice drugiego rzędu można rozstrzygać w czasie liniowym na wykresach ograniczonej szerokości . Jest to jedno z najbardziej znanych algorytmicznych meta-twierdzeń. Zmotywowany twierdzeniem Courcelle, wysunąłem następujące przypuszczenie: Przypuszczenie : Niech będzie dowolną właściwością definiowaną przez MSO. Jeśli ψ można rozwiązać …
1
Czy SAT w ograniczonej szerokości jest rozstrzygalny w przestrzeni logów?
Elberfeld, Jakoby i Tantau 2010 ( ECCC TR10-062 ) dowiodły, że zajmująca mało miejsca wersja twierdzenia Bodlaendera. Wykazali, że w przypadku wykresów o szerokości co najwyżej rozkład drzewa o szerokości k można znaleźć za pomocą przestrzeni logarytmicznej. Stały współczynnik w ograniczonej przestrzeni zależy od k . (Twierdzenie Bodlaendera pokazuje liniowe …
1
Klasy wykresów z nadprzyrodzoną szerokością
Istnieje kilka interesujących klas wykresów z ograniczoną szerokością. Na przykład drzewa (treewidth 1), szeregi równoległe wykresy (treewidth 2), zewnętrzne płaszczyzny (treewidth 2), routerplanar wykresy (treewidth O (k)), wykresy szerokości gałęzi (treewidth O (k)), .. .kkkkkk Pytanie: Czy istnieją przykłady interesujących klas wykresów, których szerokość nie jest ograniczona stałą, ale funkcją …
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.