Pytania otagowane jako graph-algorithms

Algorytmy na wykresach, z wyłączeniem heurystyki.

6
Kiedy mówi się, że dwa algorytmy są „podobne”?
Nie pracuję w teorii, ale moja praca wymaga od czasu do czasu czytania (i rozumienia) prac teoretycznych. Kiedy zrozumiem (zestaw) wyników, omawiam je z ludźmi, z którymi pracuję, z których większość również nie działa w teorii. Podczas jednej z takich dyskusji pojawiło się następujące pytanie: Kiedy mówi się, że dwa …
2
Znajdowanie k najkrótszych ścieżek za pomocą algorytmu Eppsteina
Próbuję dowiedzieć się, jak działa wykres ścieżki według algorytmu Eppsteina w tym artykule i jak mogę zrekonstruować najkrótszych ścieżek od do z odpowiednią konstrukcją stosu .k s t H ( G )P(G)P(G)P(G)kkkssstttH(G)H(G)H(G) Jak dotąd: out(v)out(v)out(v) zawiera wszystkie krawędzie opuszczające wierzchołek na wykresie , które nie są częścią najkrótszej ścieżce . …
1
Zmniejszanie rozkładu drzewa o minimalnej szerokości w czasie wielomianowym
Jak dobrze wiadomo, rozkład drzewa wykresu składa się z drzewa ze skojarzoną torbą dla każdego wierzchołka , który spełnia następujące warunki:T T v ⊆ V ( G ) v ∈GGGTTTTv⊆V(G)Tv⊆V(G)T_v \subseteq V(G)v∈V(T)v∈V(T)v \in V(T) Każdy wierzchołek występuje w jakimś workiem .TGGGTTT Dla każdej krawędzi znajduje się worek zawierający oba punkty …
1
Jak nazywa się ten problem z grafem skierowanym?
Wykonaj ukierunkowany wykres gdzie krawędzie są ozdobione naturalną liczbą. Chcemy zestawu wszystkich ścieżek między dwoma wierzchołkami v 1 i tak aby każda kolejna krawędź ścieżki była ozdobiona liczbą naturalną, która jest większa niż liczba naturalna dekorująca poprzednią krawędź.GGGv 2P.P.Pv1v1v_1v2)v2)v_2 Przykładem może być rozkład jazdy autobusów lub pociągów. Jeśli próbujesz ustalić …
1
2FA złożoność stanu k-Clique?
W prostej formie: Można dwukierunkowa skończony automat rozpoznaje vvv wykresy -Vertex które zawierają trójkąt z o(v3)o(v3)o(v^3) stany? Detale Zainteresowania są tu vvv wykresy -Vertex kodowane przy użyciu sekwencji krawędzi, każda krawędź jest para różnych wierzchołki {0,1,…,v−1}{0,1,…,v−1}\{0,1,\dots,v-1\} . Załóżmy, że (Mv)(Mv)(M_v) jest ciągiem dwukierunkowy automaty skończone (deterministyczny lub niedeterministyczny), tak że …
2
Biorąc pod uwagę 4-cyklowy wykres , czy możemy ustalić, czy ma on 3-cykl w czasie kwadratowym?
Problem z rowem jest następujący:kkk Instancja: Niekierowany wykres z wierzchołkami i do n \ wybierz 2 krawędzie.nsolsolGnnn( n2))(n2))n \choose 2 Pytanie: Czy w G istnieje (właściwy) cykl K ?kkksolsolG Tło: Dla każdego ustalonego kkk możemy rozwiązać cykl 2 tys2)k2k w czasie O ( n2))O(n2))O(n^2) . Raphael Yuster, Uri Zwick: Znalezienie …
1
Czy ta gęsta wersja algorytmu Kruskala jest dobrze znana?
Mniej więcej rok temu razem z przyjacielem zastanawialiśmy się, jak zaimplementować algorytm Kruskala dla gęstych wykresów w lepszej niż zwykle granicy O ( m logm )O(mlog⁡m)O(m \log m) (bez zakładania wstępnie posortowanych krawędzi). Konkretnie, osiągamy Θ ( n2))Θ(n2))\Theta(n^2) we wszystkich przypadkach, podobnie jak Prim, gdy implementujemy je za pomocą macierzy …
1
Modułowy rozkład i szerokość kliki
Próbuję zrozumieć niektóre pojęcia dotyczące rozkładu modułowego i wykresów szerokości kliki . W tym artykule („Na wykresach uporządkowanych za pomocą P4”) znajduje się dowód na to, jak rozwiązać problemy z optymalizacją, takie jak liczba kliki lub liczba chromatyczna za pomocą rozkładu modułowego. Rozwiązanie tych problemów przez skomponowanie (przy użyciu sumy …
3
Super Mario płynie w NP?
Klasycznym rozszerzeniem problemu maksymalnego przepływu jest problem „maksymalnego przepływu w czasie”: otrzymujesz wykrój, którego dwa węzły są rozróżniane jako źródło i zlew, przy czym każdy łuk ma dwa parametry, wydajność na czas i opóźnienie. Jesteś również biorąc pod uwagę horyzont czasowy . Celem jest, aby obliczyć przepływ w czasie której …
1
Rozkłady grafów do łączenia „lokalnych” funkcji etykietowania wierzchołków
∑x∏i j ∈ Efa( xja, xjot)∑x∏jajot∈mifa(xja,xjot)\sum_x \prod_{ij \in E} f(x_i,x_j)maxx∏i j ∈ Efa( xja, xjot)maxx∏jajot∈mifa(xja,xjot)\max_x \prod_{ij \in E} f(x_i,x_j) Gdzie Max lub suma przejmuje wszystkie labelings z , produkt wprowadza się na wszystkie krawędzie dla grafu G = \ {V, E \} i f jest dowolną funkcją. Ilość ta jest …
2
Dodaj dopasowanie do ścieżki hamiltonianu, aby zmniejszyć maksymalną odległość między podanymi parami wierzchołków
Jaka jest złożoność następującego problemu? Wejście : aścieżka hamiltonowskaw K nHH.HKnKnK_n podzbiór par wierzchołkówR⊆[n]2R⊆[n]2R \subseteq [n]^2 dodatnia liczba całkowita kkk Pytanie : czy istnieje pasujące , że dla każdego ( v , u ) ∈ R , d G ( v , u ) ≤ k ? (gdzie G = …
1
Czy najdłuższy problem szlaku jest łatwiejszy niż problem najdłuższej ścieżki?
Najdłuższy problem ze ścieżką to trudność NP. (Typowy?) Dowód polega na zmniejszeniu problemu ścieżki hamiltonowskiej (która jest NP-zupełna). Zauważ, że tutaj ścieżka jest uważana za (węzłową) prostą. Oznacza to, że żaden wierzchołek nie może wystąpić więcej niż jeden raz na ścieżce. Oczywiście jest to również proste dla krawędzi (żadna krawędź …
2
Teoretyczne gwarancje dla czasów działania metod propagowania przekonań?
Wykazano, że propagacja przekonań jest bardzo skuteczną metodą dzięki badaniom w probabilistycznych modelach graficznych. Jednak nie wiem nic o BP, które byłoby porównywalne z metodami MCMC, w których możemy mieć w pełni wielomianowe losowe schematy aproksymacji (FPRAS) dla problemów z # P-zupełnością. Czy ktoś mógłby wskazać mi jakieś odniesienia?
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, …
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.