Pytania otagowane jako ds.algorithms

Pytania dotyczące dobrze zdefiniowanych instrukcji wykonania zadania oraz odpowiedniej analizy pod względem czasu / pamięci / itp.

1
Szybki splot nad małymi skończonymi polami
Jakie są najbardziej znane metody cyklicznego splotu długości na małym polu, tj. Kiedy | F | « N ? Szczególnie interesują mnie pola o stałej wielkości, a nawet F = F 2 . Doceniane są ogólne stwierdzenia i referencje dotyczące skuteczności asymptotycznej.nnn|F|≪n|F|≪n|\mathbb{F}| \ll nF=F2F=F2\mathbb{F} = \mathbb{F}_2 Tło: Niech będzie polem, …
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) …
3
Czy istnieje algorytm aproksymacji stałego współczynnika dla problemu kolorowania prostokąta 2D?
Problem, który rozważamy tutaj, to rozszerzenie znanego problemu kolorowania interwałów. Zamiast przedziałów uważamy prostokąty o bokach równoległych do osi. Celem jest pokolorowanie prostokątów przy użyciu minimalnej liczby kolorów, tak aby każdemu z dwóch nachodzących na siebie prostokątów przypisano różne kolory. Ten problem jest znany jako trudny dla NP. Xin Han, …
3
Formalna reprezentacja pierścieni w obliczeniach
Czytając artykuł na temat stosowania metod algebraicznych do wykrywania niektórych indukowanych subgrafów, okazuje się, że ideał krawędzi jest ważnym narzędziem łączącym algebrę komutacyjną i teorię grafów. Skoro nie znam obliczeń obiektów algebraicznych, czy są jakieś dobre odniesienia lub książki na ten temat? Szczególność w reprezentowaniu pierścienia R na maszynie Turinga …
3
Edytuj odległość między dwiema partycjami
Mam dwie partycje [1…n][1…n][1 \ldots n] i szukam odległości edycji między nimi. W ten sposób chcę znaleźć minimalną liczbę pojedynczych przejść węzła do innej grupy, które są niezbędne do przejścia z partycji A na partycję B. Na przykład odległość od {0 1} {2 3} {4}do {0} {1} {2 3 4}wynosi …
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 …
1
Obliczanie parzystości permutacji w sposób strumieniowy
Szukam algorytmu jednoprzebiegowego, który oblicza parzystość permutacji. Zakładam, że permutacja wejściowa jest podawana przez strumień . Wyjście powinno być parzystością permutacji. Pytanie mnie interesuje, ile pamięci powinien użyć algorytm deterministyczny. Czy istnieje jakiś losowy algorytm dotyczący problemu?π[1],π[2],⋯,π[n]π[1],π[2],⋯,π[n]\pi[1], \pi[2], \cdots, \pi[n] Wiem, że obliczanie liczby inwersji w jednym przebiegu wykorzystuje pamięć …
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 …
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.