To pytanie jest związane z jednym z moich wcześniejszych pytań, trudnymi NP na drzewach . Szukam problemów, które są kompletne P na
W swojej pracy odległości około Oracles , Thorup i Zwick wykazały, że dla każdego wykresu ważonej nieukierunkowane, możliwe jest skonstruowanie struktury danych o rozmiarze , które mogą powrócić do -approximate odległość między dowolną parą wierzchołków na wykresie.O ( k n1 + 1 / k)O(kn1+1/k)O(k...
Zarówno GI, jak i Knot Problem stanowią problem decydowania o równoważności strukturalnej obiektów matematycznych. Czy są jakieś wyniki ustanawiające powiązania między nimi? Ładne powiązania problemu węzłów z fizyką statystyczną zostały zbadane za pomocą wielomianów węzłów , czy istnieją podobne...
Zastanawiam się, jak znaleźć obwód rzadkiego niekierowanego wykresu. Przez rzadki mam na myśli . Przez optymalne rozumiem najmniejszą złożoność czasową.|E|=O(|V|)|E|=O(|V|)|E|=O(|V|) Myślałem o pewnej modyfikacji algorytmu Tarjana dla niekierowanych grafów, ale nie znalazłem dobrych wyników....
Paley wykresy P P są takie, których wierzchołek osadzone jest przez skończonego GF (q) dla pierwszego mocarstw q≡1 mod (4), w których dwa wierzchołki przylega wtedy i tylko wtedy, gdy różnią się o 2 do niektórych a ∈ GF (q). W przypadku, gdy q jest liczbą pierwszą, skończone pole GF (q) jest tylko...
To jest pytanie, zainspirowany problemu cięcia H-darmo . Biorąc pod uwagę wykres, podział jego zbioru wierzchołków na r części V 1 , V 2 , … , V r jest wolny od H, jeśli G [ V i ] nie indukuje kopii H dla wszystkich i , 1 ≤ i ≤ r .VVVrrrV1,V2,…,VrV1,V2,…,VrV_1, V_2, \ldots,...
Interesuje mnie zrozumienie struktury klasy grafów taki sposób, że na czterech wierzchołkach nie ma podgraphu indukowanego wierzchołkiem, który jest idealnym dopasowaniem. Zaznaczono inaczej, dla wszystkich czterech wierzchołkach , b , c , d , w G jeśli b i c d są krawędzie to wykres powinien...
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...
Dla których niekierowanych wykresów są wszystkie drzewa pierwszego wyszukiwania głębokości (dla wszystkich możliwych wierzchołków początkowych i dla wszystkich wyborów, których sąsiadów najpierw szukać) ścieżki skierowane? Oznacza to, że każde drzewo DFS powinno mieć tylko jeden liść, a każdy inny...
Załóżmy, że mamy zestaw S grafów (wykresy skończone, ale ich nieskończona liczba) i grupę P permutacji, która działa na S. Instancja: permutacja pw P. Pytanie: Czy istnieje wykres g w S, który dopuszcza automorfizm p? Czy ten problem NP-zupełny dla niektórych zestawów S? Łatwo byłoby...
Niech będzie klasą grafów z ograniczoną szerokością kliki. Na każdym wykresie w G niektóre krawędzie są skurczone (np. Losowo). Czy teraz szerokość kliki jest nadal ograniczona?solGGsolGG W przypadku, gdy (ogólnie) nie jest już ograniczony, byłbym bardzo zainteresowany...
W przypadku problemu z rozszerzeniem otrzymujemy część rozwiązania i chcemy zdecydować, czy możemy go rozszerzyć do kompletnego rozwiązania. Niektóre problemy związane z rozszerzalnością można skutecznie rozwiązać, podczas gdy inne problemy z możliwością rozbudowy przekształcają problem łatwy w...
Próbowałem następującej relaksacji LP maksymalnie niezależnego zestawu max∑iximax∑ixi\max \sum_i x_i s.t. xi+xj≤1 ∀(i,j)∈Es.t. xi+xj≤1 ∀(i,j)∈E\text{s.t.}\ x_i+x_j\le 1\ \forall (i,j)\in E xi≥0xi≥0x_i\ge 0 Dostaję 1/21/21/2 za każdą zmienną za każdy sześcienny dwudzielny wykres, który...
W Bundeswettberweb Infomatik 2010/2011 pojawił się interesujący problem: Dla stałej znajdź minimalne i mapę , tak że nie ma potrójnego z .nnnkkkφ:{(i,j)|i≤j≤n}→{1,…,k}φ:{(i,j)|i≤j≤n}→{1,…,k}\varphi: \{(i,j)|i\leq j \leq n\}\rightarrow
Kontekst To pytanie jest motywowane grą planszową o nazwie „Dracula”. W tej grze jest jeden wampir i czterech łowców, których celem jest złapanie wampira. Gra toczy się w Europie. Gra wygląda następująco: 1. Łowca umieszcza wszystkich łowców w miastach. W tym samym mieście można umieścić więcej...
Dana jest skierowany acykliczny wykres o numer przypisany do każdego wierzchołka ( g : V → N ), i docelową liczbą T ∈ N .G=(V,E)G=(V,E)G=(V,E)g:V→Ng:V→Ng:V\to \mathbb{N}T∈NT∈NT\in \mathbb{N} Problem sumy podzbioru DAG (może występować pod inną nazwą, odniesienie będzie wielki) pyta, czy istnieją...
Chong, Han i Lam pokazali, że nieukierunkowaną łączność st można rozwiązać na EREW PRAM w czasie pomocą procesorów O ( m + n ) .O(logn)O(logn)O({\log}n)O(m+n)O(m+n)O(m+n) Jaki jest najbardziej znany algorytm równoległy dla łączności st w ukierunkowanych grafach płaskich? Podaj czas działania,...
W tym artykule Kempe-Kleinberg-Tardos autorzy proponują zachłanne algorytmy oparte na funkcjach submodularnych w celu określenia najbardziej wpływowych węzłów na wykresie, z zastosowaniem do sieci społecznościowych.kkk Zasadniczo algorytm wygląda następująco: S=empty setS=empty setS = {\rm...
Biorąc pod uwagę wykres płaski, można go osadzić w liniowym czasie przechodzącym swobodnie w siatkę . Interesuje mnie, czy znane są efektywne algorytmy linii prostej osadzającej płaski wykres przecinający się swobodnie w siatce n c × n c , dla jakiegoś małego c , tak, że minimalny kąt między dwiema...
Załóżmy, że istnieje wykres . Chcę sprawdzić, czy można podzielić na dwa rozłączne zestawy i tak, że podgrupy indukowane przez i są wykresami interwałów jednostkowych.G=(V,E)G=(V,E)G=(V,E)VVVV1V1V_1V2V2V_2V1V1V_1V2V2V_2 Wiem o kompletności NP określania liczb przedziałów, ale powyższy problem jest...