Pytania otagowane jako graph-minor

5
co jest łatwe dla niewielkich wykluczonych wykresów?
Przybliżenie liczby kolorów wydaje się łatwe na niewielkich wykluczonych wykresach przy użyciu algorytmu Jung / Shah. Jakie są inne przykłady problemów, które są trudne na ogólnych wykresach, ale łatwe na niewielkich wykluczonych wykresach? Aktualizacja 10/24 Wydaje się, że podąża za wynikami Grohe, że wzór, którym jest FPT do testowania na …
1
Niewielkie zamknięte właściwości, które są wyraźnie wyrażalne przez MSO
Poniżej MSO oznacza monadyczną logikę drugiego rzędu grafów z kwantyfikacjami zbioru wierzchołków i zbocza. Niech będzie niewielką zamkniętą rodziną grafów. Z teorii drugorzędnej grafu Robertsona i Seymour wynika, że charakteryzuje się skończoną listą zakazanych nieletnich. Innymi słowy, dla każdego wykresu mamy, że należy do wtedy i tylko wtedy, gdy wyklucza …
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 …
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
Zabronione osoby niepełnoletnie w przypadku związanych z nimi wykresów rodzajów
Powszechnie wiadomo, że i K 3 , 3 są niedozwolone w przypadku wykresów planarnych. Istnieją setki zakazanych nieletnich dla wykresów osadzanych na torusie. Liczba niedozwolonych nieletnich dla wykresów osadzanych na powierzchni rodzaju g jest funkcją wykładniczą g . Moje pytanie brzmi:K5K5K_5K3,3K3,3K_{3,3} Ma wyraźnego wykresem o t wierzchołków (co nie jest …
1
Liczba 4 cykli
Niech C4C4C_4 będzie cyklem z czterema wierzchołkami. Aby uzyskać dowolny wykres GGG z nnn wierzchołkami i krawędziami m, powiedz m>nn−−√m>nnm>n\sqrt n , ileistniejeC4C4C_4? Czy jest na to dolna granica?
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
Cytowanie pokazujące osoby niepełnoletnie są nieletnimi topologicznymi dla wykresów podrzędnych
Jeśli jest wykresem w stopniu maksymalnie 3 i jest minor H , a G jest topologiczna minor H .solGGH.HHsolGGH.HH Wikipedia cytuje ten wynik z „Teorii grafów” Diestela. Jest wymieniony jako Prop 1.7.4 w najnowszej wersji książki. W książce brakuje dowodu lub cytowania. Czy miejsce pobytu znane jest z (oryginalnego) dowodu …
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 istnieje algorytm, który wyszukuje zakazanych nieletnich?
Twierdzenie Robertsona-Seymour'a głosi, że każda niewielka, zamknięta rodzinasolG\mathcal G wykresów można scharakteryzować przez skończoną liczbę zakazanych nieletnich. Czy istnieje algorytm wejściowy solG\mathcal G wypuszcza zakazanych nieletnich, czy jest to nierozstrzygalne? Oczywiście odpowiedź może zależeć od tego, w jaki sposób solG\mathcal Gjest opisany na wejściu. Na przykład jeślisolG\mathcal G jest podany …
1
Znajdowanie podgrafów o wysokiej szerokości i stałym stopniu
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 tak że na dowolnym wykresieGGG kkkHHHGGGHHHd∈Nd∈Nd …
2
Zrozumienie graficznego mniejszego twierdzenia
To pytanie jest dwojakie i dotyczy głównie odniesienia: Czy jest gdzieś, gdzie podane są główne intuicje dowodzenia niewielkiego twierdzenia o grafie, bez zbytniego zagłębiania się w szczegóły? Wiem, że dowód jest długi i trudny, ale z pewnością muszą istnieć kluczowe pomysły, które można przekazać w łatwiejszy sposób. Czy istnieją inne …
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.