Pytania otagowane jako graph-algorithms

Algorytmy na wykresach, z wyłączeniem heurystyki.

2
Problemy z kratą
Dużo pracy poświęcono problemom obliczeniowym dla zamówień częściowych (np. Rozpoznawanie, numer skoku, rozpoznawanie wykresu porównywalności itp.). Jestem ciekawy, jaką pracę wykonano dla sieci. Szukałem wokoło i nie znalazłem podobnej pracy dla krat. W szczególności jestem zainteresowany tym, czy zbadano następujące problemy z siecią: Rozpoznawanie krat: czy przy danym DAG czy …
1
Czy istnieje algorytm wielomianowy do rozwiązywania izomorfizmu grafów dla grafów Delaunaya (skończonych) heksagonalnych teselacji?
Biorąc pod uwagę skończoną płaszczyznę, mam sześciokątną teselację tej płaszczyzny z regularnym sześciokątem o stałej wielkości. Następnie obliczam wykres G Delaunaya dla teselacji. Biorąc pod uwagę taki wykres G, usuwam określone zestawy węzłów na tym wykresie, aby uzyskać wiele podgraphów G. Muszę ustalić, czy podgrupy te są izomorficzne (względem siebie). …
1
Przycinanie silnie połączonego digrafa
Biorąc pod uwagę silnie połączony wykres G z ważonymi krawędziami, chciałbym zidentyfikować krawędzie, które prawdopodobnie nie są częścią żadnego minimalnie silnie połączonego podgrupy (MSCS) G. Jedną z metod znajdowania takich krawędzi jest zmodyfikowany algorytm Floyda-Warshalla. Korzystając z algorytmu Floyda-Warshalla, można określić, które krawędzie nigdy nie są najlepszą opcją przejścia od …
1
Znalezienie krótkich i grubych ścieżek
Motywacja: W standardowych algorytmach maksymalnego przepływu ścieżki augmentacyjnej wewnętrzna pętla wymaga znalezienia ścieżek od źródła do zatonięcia na ukierunkowanym, ważonym wykresie. Teoretycznie dobrze wiadomo, że aby algorytm nawet zakończył działanie, gdy istnieją nieracjonalne pojemności krawędzi, musimy nałożyć ograniczenia na ścieżki, które znajdziemy. Na przykład algorytm Edmondsa-Karpa mówi nam, aby znaleźć …
2
Jak długo trwa znalezienie krótkiego cyklu na losowym wykresie?
Pozwolić G∼G(n,n−1/2)G∼G(n,n−1/2)G \sim G(n, n^{-1/2}) być losowym wykresem na ≈n3/2≈n3/2\approx n^{3/2}krawędzie Z bardzo dużym prawdopodobieństwemGGG ma wiele 444motocykle. Naszym celem jest wyprodukowanie dowolnego z nich444- motocykle tak szybko, jak to możliwe. Załóżmy, że mamy dostęp do GGG w formie listy sąsiedztwa możemy odnieść sukces ze stałym prawdopodobieństwem w O(n−−√)O(n)O(\sqrt{n}) czas …
2
Kontrprzykład do algorytmów maksymalnego przepływu z irracjonalnymi wagami?
Wiadomo, że Ford-Fulkerson lub Edmonds-Karp z heurystyczną grubą rurą (dwa algorytmy dla maksymalnego przepływu) nie muszą się zatrzymywać, jeśli niektóre ciężary są nieracjonalne. W rzeczywistości mogą nawet zbierać się na niewłaściwej wartości! Jednak wszystkie przykłady, które mogłem znaleźć w literaturze [odnośniki poniżej oraz odnośniki w nich] wykorzystują tylko jedną wartość …
1
Czy znana jest złożoność tego problemu ścieżki?
Instancja: Niekierowany wykresGGGz dwoma wyróżnionymi wierzchołkami i liczbą całkowitą .s≠ts≠ts\neq tk≥0k≥0k\geq 0 Pytanie: Czy istnieje ścieżka w , taka, że ​​przecina ona co najwyżej trójkątów? (W przypadku tego problemu mówi się, że ścieżka przecina trójkąt, jeśli ścieżka zawiera co najmniej jedną krawędź od trójkąta).s−ts−ts-tGGGkkk
1
Dopasowanie masy „sprawiedliwe”
Interesuje mnie wariant maksymalnego dopasowania wagi na wykresie, który nazywam „maksymalnym uczciwym dopasowaniem”. Załóżmy, że wykres jest pełny (tj E=V×VE=V×VE=V\times V) Ma liczbę nawet wierzchołków, a masa jest podawana przez funkcję zysk . Biorąc pod uwagę pasujące , oznacz przez zysk krawędzi jest dopasowany.p:(V2)→Np:(V2)→Np:{V\choose 2}\to \mathbb NMMMM(v)M(v)M(v)vvv Pasujące jest sprawiedliwym …
2
Wyliczanie płaskich wykresów ograniczonej szerokości poprzecznej
Szukam odniesień do następującego problemu: biorąc pod uwagę liczby całkowite i , wyliczyć wszystkie nieizomorficzne wykresy płaskie na wierzchołkach i szerokości linii . Interesują mnie zarówno wyniki teoretyczne, jak i praktyczne, ale przede wszystkim praktyczne algorytmy, które można kodować i uruchamiać dla możliwie dużych wartości i (pomyśl i ). Jeśli …
1
Znajdowanie podobnych wektorów w czasie subkwadratowym
Pozwolić d:{0,1}k×{0,1}k→Rd:{0,1}k×{0,1}k→Rd:\{0,1\}^k\times \{0,1\}^k \to \mathbb{R}być funkcją, którą nazywamy funkcją podobieństwa . Przykłady funkcji podobieństwa to odległość cosinus,l2l2l_2 norma, odległość Hamminga, podobieństwo Jaccard itp. Rozważać nnn binarne wektory długości kkk: v⃗ ∈({0,1}k)nv→∈({0,1}k)n\vec{v} \in (\{0,1\}^k)^n. Naszym celem jest grupowanie wektorów, które są podobne. Bardziej formalnie chcemy obliczyć wykres podobieństwa, w którym węzły …
2
Obliczanie przejściowego zakończenia / wyroku istnienia ścieżki
Było kilka pytań ( 1 , 2 , 3 ) na temat przechodniego uzupełniania, które zmusiły mnie do zastanowienia się, czy coś takiego jest możliwe: Załóżmy, że otrzymujemy wykres skierowany na dane wejściowe GsolG i chciałby odpowiedzieć na zapytania typu „(u,v)∈G+(u,v)∈sol+(u,v)\in G^+? ”, tzn. pytając, czy istnieje krawędź między dwoma …
2
Liczba cykli na wykresie
Ile cykli CkCkC_k (k≥3)(k≥3)(k \geq 3) znajdują się na wykresie wierzchołków, tak że wykres nie ma żadnego cyklu .nnn CmCmC_m (m>k)(m>k)(m>k) Na przykład , , wówczas wykres będzie miał najwyżej dwa , tak że nie będzie miał żadnegon=5n=5n=5k=3k=3k=3C3C3C_3GGGCk(k>3).Ck(k>3).C_k (k > 3). Myślę, że są O(n)O(n)O(n) cykle będą tam spełniające powyższe …
1
Znalezienie optymalnej równoległości z ogólnego ważonego niekierowanego wykresu
Rozwiązuję problem „mieszania” zestawów nakładających się obrazów. Te zestawy mogą być reprezentowane przez niekierowany ważony wykres, taki jak ten: Każdy węzeł reprezentuje obraz. Nakładające się obrazy są połączone krawędzią. Ciężar krawędzi reprezentuje wielkość obszaru nakładania się ( wcześniejsze połączenie większego nakładania prowadzi do lepszej ogólnej jakości ). Algorytm ogólnie usuwa …
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.