Pytania otagowane jako graph-algorithms

Algorytmy na wykresach, z wyłączeniem heurystyki.

1
Przybliżenie do zliczania liczby prostych ścieżek
I powiedziano, że istnieją dobre wielomianowe algorytmy czasu dla zbliżenia liczbę prostych odcinków w skierowanej wykresie począwszy od danego wierzchołka do danego zakończony wierzchołek T . Czy ktoś zna dobre referencje na ten temat?sssttt Tło: zliczanie dokładnej liczby ścieżek na ogólnym wykresie jest # P-pełne, ale mogą istnieć przybliżone wielomianowe …
2
Sparametryzowana złożoność numeru przecięcia wykresu
Co jeśli wiadomo o sparametryzowanej złożoności obliczania numeru przecięcia wykresu (najmniejszej liczby klików potrzebnych do pokrycia wszystkich jego krawędzi)? Od dawna wiadomo, że jest NP-kompletny, i oczywiście FPT, ponieważ ma jądro: jeśli możesz pokryć wykres klikami, to istnieje co najwyżej różnych zamkniętych sąsiedztw wierzchołków (dwa wierzchołki mają te same sąsiedztwa …
2
Czy istnieje algorytm do skutecznego utrzymywania informacji o połączeniach dla DAG w przypadku wstawiania / usuwania?
Biorąc pod uwagę ukierunkowany wykres acykliczny, G(V,E)G(V,E)G(V,E) , czy można skutecznie obsługiwać następujące operacje? : Określa, czy w G istnieje ścieżkaod węzła a do węzła bisConnected(G,a,b)isConnected(G,a,b)isConnected(G,a,b)GGGaaabbb : Dodaje krawędź od a do b na wykresie Glink(G,a,b)link(G,a,b)link(G,a,b)aaabbbGGG : Usuwa krawędź od a do b w Gunlink(G,a,b)unlink(G,a,b)unlink(G,a,b)aaabbbGGG : Dodaje wierzchołek do Gadd(G,a)add(G,a)add(G,a) …
1
Jaka jest złożoność tego problemu z grafem?
Biorąc pod uwagę prosty niekierowany wykres GGG , znajdź podzbiór A≠∅A≠∅A\neq \emptyset wierzchołków, taki jak dla dowolnego wierzchołka x∈Ax∈Ax\in A co najmniej połowa sąsiadów xxx również znajduje się w AAA i rozmiar AAA jest minimalny. Oznacza to, że szukamy gromady, w której co najmniej połowa sąsiedztwa każdego wewnętrznego wierzchołka pozostaje …
1
Odniesienie do algorytmu testowania acykliczności mieszanego grafu?
Wykres mieszany to wykres, który może mieć zarówno skierowane, jak i nieukierowane krawędzie. Podstawowy nieukierowany wykres jest uzyskiwany przez zapomnienie orientacji skierowanych krawędzi, a w drugim kierunku orientacja mieszanego wykresu jest uzyskiwana przez przypisanie kierunku każdej nieukierunkowanej krawędzi. Zestaw krawędzi tworzy cykl na wykresie mieszanym, jeśli można go zorientować w …
2
Złożoność czasowa liczenia trójkątów na wykresach płaskich
Liczenie trójkątów na ogólnych wykresach można trywialnie wykonać w czasie i myślę, że znacznie szybsze wykonanie jest trudne (mile widziane referencje). Co z grafami płaskimi? Poniższa prosta procedura pokazuje, że można tego dokonać w czasie O ( n log n ) . Moje pytanie jest dwojakie:O(n3)O(n3)O(n^3)O(nlogn)O(nlog⁡n)O(n\log{n}) Jakie jest odniesienie do …
2
Złożoność zliczania liczby okładek krawędzi wykresu
Osłona krawędzi jest podzbiorem krawędzi wykresu, tak że każdy wierzchołek wykresu sąsiaduje z co najmniej jedną krawędzią okładki. Poniższe dwa artykuły mówią, że liczenie krawędzi jest zakończone #P : Prosty FPTAS do zliczania krawędzi i generowania krawędzi krawędzi wykresów ścieżek . Jednakże, chyba że coś przeoczyłem, nie zawierają one odniesienia …
4
Problemy z grafem, które są NP-Complete na grafach ukierunkowanych, ale wielomianowe na grafach niekierowanych
Szukam problemów, które są znane jako NPC dla grafów kierowanych, ale mają algorytm wielomianowy dla grafów bezkierunkowych. Widziałem pytanie dotyczące odwrotnych problemów, które są łatwiejsze niż ich „niekierowany” wariant , ale szukam twardości po stronie ukierunkowanej. Na przykład, zestaw krawędzi sprzężenia zwrotnego jest znany jako NPC na ukierunkowanych, ale wielomianowych …
2
Informacje o uogólnionych grafach płaskich i uogólnionych grafach zewnętrznych płaszczyzn
Każdy płaski odpowiednio outerplanar wykres spełnia , odpowiednio | E ′ | ≤ 2 | V ′ | - 3 dla każdego podgrafu G ' = ( V ' , E ' ) z G . Również (zewnętrzne) wykresy płaskie można rozpoznać w czasie wielomianowym.G=(V,E)G=(V,E)G=(V,E)|E′|≤3|V′|−6|E′|≤3|V′|−6|E'|\le 3|V'|-6|E′|≤2|V′|−3|E′|≤2|V′|−3|E'|\le 2|V'|-3G′=(V′,E′)G′=(V′,E′)G'=(V',E')GGG Co wiadomo na …
1
Jaki jest najszybszy algorytm deterministyczny dla dynamicznej osiągalności digrafu bez usuwania krawędzi?
Jaki jest najlepszy wynik deterministyczny dla utrzymania dynamicznego zamknięcia przechodniego na ukierunkowanym wykresie z tylko wstawieniem krawędzi? Przeczytałem kilka artykułów na temat problemu dynamicznego zamykania przechodniego zarówno przy wstawianiu, jak i usuwaniu krawędzi. Czy są jednak lepsze algorytmy z tylko wstawianiem krawędzi?
3
Najmniejszy zbiór, który przecina niektóre podane zbiory
Niech będą zestawami, które mogą mieć wspólne elementy. Szukam najmniejszego zestawu takiego, że .S1,S2,…,SnS1,S2,…,SnS_1,S_2,\ldots,S_nXXX∀i,X∩Si≠∅∀i,X∩Si≠∅\forall i,\,X\cap S_i \ne \emptyset Czy ten problem ma nazwę? Czy może sprowadza się to do znanego problemu? W moim kontekście opisują elementarne cykle silnie połączonego komponentu i szukam najmniejszego zestawu wierzchołków który przecina wszystkie cykle.S1,…,SnS1,…,SnS_1,\ldots,S_nXXX
4
Sparametryzowany algorytm znajdowania biklików
Biorąc pod uwagę nieukierowany wykres nnn wierzchołka, jaki jest najbardziej znany środowisko uruchomieniowe dla znalezienia podrozdziału, który jest dwukolorową k × kk×kk\times k ? Czy istnieją szybsze algorytmy parametryzowane niż algorytm polegający na „zgadywaniu” jednej strony biclique i sprawdzanie, czy występuje co najmniej k innych wierzchołków przypadających na wszystkie z …
2
Reprezentowanie wykresów niepłaskich z nakładającymi się okręgami
Wiemy, że możemy przedstawić dowolny wykres płaski za pomocą zestawu kół w płaszczyźnie, znanego jako wykres monety . Każde koło reprezentuje wierzchołek, a pomiędzy dwoma wierzchołkami znajduje się krawędź wtedy i tylko wtedy, gdy koła „pocałują się” na swojej granicy. Załóżmy, że zamiast tego zezwalamy na nakładanie się kół i …
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.