Pytania otagowane jako graph-algorithms

Algorytmy na wykresach, z wyłączeniem heurystyki.

3
NP-pełna właściwość graficzna, która jest dziedziczna, ale nie addytywna?
Właściwość wykresu jest nazywana dziedziczną, jeśli zostanie zamknięta w odniesieniu do usuwania wierzchołków (tj. Wszystkie indukowane podgrupy dziedziczą właściwość). Właściwość graf nazywa się addytywną, jeśli jest zamknięta w odniesieniu do przyjmowania rozłącznych związków. Nie jest trudno znaleźć właściwości dziedziczne, ale nie addytywne. Dwa proste przykłady: \;\;\;(1) Wykres jest kompletny. \;\;\;(2) …
3
Podgraf zawierający wszystkie węzły i krawędzie, które są częścią prostych ścieżek st o ograniczonej długości na niekierowanym wykresie
Całkiem podobne do mojego wcześniejszego pytania . Tym razem jednak wykres nie jest przekierowany. Dany Nieukierunkowane wykres solGG bez wielu krawędzie lub pętli Źródło wierzchołek sss , Docelowy wierzchołek ttt , Maksymalna długość ścieżki lll , Szukam sol′G′G' - podgraf solGG który zawiera dowolny wierzchołek i dowolną krawędź w solGG …
2
Mały wykres z odstępem między liczbą chromatyczną a liczbą chromatyczną wektorową?
Szukam małego wykresu GGG którego wektorowa liczba chromatyczna jest mniejsza niż liczba chromatyczna, χv(G)&lt;χ(G)χv(G)&lt;χ(G)\chi_v(G)<\chi(G) . ( GGG zawiera wektor chromatycznej liczba qqq , jeśli istnieje zadanie x:V→Rdx:V→Rdx\colon V \rightarrow \mathbf R^d , gdzie intuicyjnie wektory związane z sąsiednimi wierzchołkami są oddalone od siebie Warunkiem jest, ⟨x(v),x(w)⟩≤−1/(q−1)⟨x(v),x(w)⟩≤−1/(q−1)\langle x(v), x(w)\rangle \leq -1/(q-1) …
1
Negatywne wyniki w podejściu identycznych cząstek do problemu Isomorphism Graph (GI)
Podjęto próby zaatakowania problemu izomorfizmu grafów za pomocą kwantowego losowego chodzenia twardych rdzeni (symetryczne, ale bez podwójnego zajęcia). Symetryczna moc matrycy przylegania, która wydawała się obiecująca, wykazano jako niekompletne ogólnych wykresów na tym papierze Amir Rahnamai Barghi i Ilia Ponomarenko. Inne podobne podejście zostało również obalone w tym artykule przez …
4
Przyrostowy maksymalny przepływ na wykresach dynamicznych
Szukam szybkiego algorytmu do obliczenia maksymalnego przepływu na wykresach dynamicznych. tzn. biorąc pod uwagę wykres i , mamy maksymalny przepływ w od do . Następnie nowy / stary węzeł dodane / usunięty z jego odpowiednich krawędziach, tworząc krzywą . Jaki jest maksymalny przepływ na nowo utworzonym wykresie? Czy istnieje sposób, …
2
Przybliżone zabarwienie wykresu z obiecaną górną granicą na maksymalnym niezależnym zestawie
W mojej pracy powstaje następujący problem: Czy istnieje znany algorytm, który aproksymuje liczbę chromatyczną wykresu bez niezależnego zestawu rzędów 65? (Więc alfa (G) &lt;= 64 jest znane, a | V | / 64 jest trywialną dolną, | V | trywialną górną granicą. Ale czy istnieją lepiej udowodnione przybliżenia w tych …
2
Maksymalne cięcie w kształcie euklidesa w małych wymiarach
x1,…,xnx1,…,xnx_1, \ldots, x_nR2R2\mathbb{R}^2∥xi−xj∥2‖xi−xj‖2\|x_i - x_j\|^22323\frac 2 32323\frac 2 3 Najgorszy przykład, jaki mogę znaleźć, to 3 punkty na równobocznym trójkącie, który osiąga . Zauważ, że losowy podział dałby , ale intuicyjnie wydaje się intuicyjnie, że w niskich wymiarach można skupić się lepiej niż losowo.2323\frac 2 31212\frac 1 2 Co się …
2
Odwołanie do szybkiego algorytmu dla najkrótszych ścieżek wąskich gardeł
Szukam dobrego odniesienia do najkrótszych ścieżek wąskich gardeł. W szczególności, biorąc pod uwagę wierzchołki si na grafie bezkierunkowym z wagami krawędzi, potrzebujesz najkrótszej ścieżki od s do t, gdzie długość ścieżki jest maksymalną krawędzią na tej ścieżce. Można to rozwiązać w czasie O (n + m), znajdując środkową masę krawędzi …
4
Jakie jest najważniejsze pojęcie rzadkości w projektowaniu wydajnych algorytmów graficznych?
Istnieje kilka konkurencyjnych pojęć „rzadkiego wykresu”. Na przykład wykres, który można osadzić na powierzchni, można uznać za rzadki. Lub wykres z ograniczoną gęstością krawędzi. Lub wykres z wysokim obwodem. Wykres z dużym rozszerzeniem. Wykres z ograniczoną szerokością. (Nawet w obrębie podpól losowych wykresów jest nieco niejednoznaczne co do tego, co …
3
Trudne problemy NP na kartografach
To pytanie jest podobne do trudnych NP problemów na drzewach : Istnieje duża liczba problemów z NP, które można rozwiązać na kartografach . Czy są jakieś znane problemy, które pozostają NP-kompletne, gdy są ograniczone do kartografów? Mówiąc ściślej, interesują mnie przykłady, w których dane wejściowe składają się wyłącznie z niekierowanego, …
2
Problemy z optymalizacją MSOL na wykresach ograniczonej płynności z predykatami liczności
CMSOL to zliczanie logiki monadycznej drugiego rzędu, tj. Logiki grafów, w których domeną jest zestaw wierzchołków i krawędzi, istnieją predykaty dla przylegania wierzchołków i wierzchołków oraz występowania krawędzi i wierzchołków, istnieje kwantyfikacja na krawędziach, wierzchołkach, zestawach krawędzi i wierzchołkach ustawia, a istnieje predykat która wyraża, czy rozmiar S jest n …
1
Typowa twardość rozkładu drzew?
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 źle się sprawdzają?
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.