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:...
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...
Zadałem to pytanie kilka tygodni temu w Mathoverflow , ale nie otrzymałem odpowiedzi. Tutaj przez siatkę 3D długości bocznej rozumiem wykres G = ( V , E ) z V = { 1 , … , k } 3 i E = { ( ( a , b , c ) , ( x , y , z ) ) ∣ | a - x | + | b - y | + | dokkkG=(V,E)G=(V,E)G=(V,E)V={1,…,k}3V={1,…,k}3V=...
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...
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ć...
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 ,...
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...
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,...
Czy istnieją jakieś ładne klasy grafów, dla których szerokość drzewa jest ograniczona górną funkcją liczby kliki , tj. ?ω ( G ) t w ( G ) ≤ f ( ω ( G ) )t w ( G )tw(G)tw(G)ω ( G )ω(G)\omega(G)t w ( G ) ≤ f( ω ( G ) )tw(G)≤f(ω(G))tw(G)\leq f(\omega(G)) Na przykład, klasycznym faktem jest, że dla...
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...
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...
za´za´\acute{\rm a}H ∈ P T I M EH.H.HH.H.H∈ P.T.jaM.mi∈P.T.jaM.mi\in PTIME Definicje itp. Świetny przegląd standardowych rozkładów drzew i ich szerokości znajduje się tutaj (Dziękujemy z góry, JeffE!). Niech H.H.H będzie hipergrafatem. Następnie dla hipergraph H.H.H i mapowania γ: E( H) → [ 0 ,...
Szukam odniesień do następującego problemu: biorąc pod uwagę liczby całkowite i , wyliczyć wszystkie nieizomorficzne wykresy płaskie na wierzchołkach i szerokości linii . Interesują mnie zarówno wyniki teoretyczne, jak i praktyczne, ale przede wszystkim praktyczne algorytmy, które można kodować i...
Najpierw zapytany na stronie math.SE bez odpowiedzi Załóżmy, że mam wykres płaski z osadzeniem planarnym, jak znaleźć rozkład drzewa? Jaki jest optymalny rozkład drzewa siatki kwadratowej -by- ? Nie do końca pewny, jak zdefiniować „optymalny”, ale powinien odróżniać rozkład z jedną dużą torbą od...
W Graphic TSP otrzymujesz nieważony niekierowany wykressolsolG a celem jest znalezienie najkrótszej trasy w solsolGktóry odwiedza każdy wierzchołek przynajmniej raz . Zauważ, że NIE jest to to samo, co znalezienie obwodu hamiltonowskiegosolsolG. Moje pytania to: Jaka jest złożoność Graphic TSP...
Dano mi wykres z szerokością i dowolnym stopniem, i chciałbym znaleźć podrozdział z (niekoniecznie indukowany podsgraf) taki, że ma stały stopień, a jego szerokość jest tak wysoka, jak to możliwe. Formalnie mój problem jest następujący: po wybraniu stopnia związanego , jaka jest najlepsza funkcja...