Pytania otagowane jako directed-acyclic-graph

Jest to struktura matematyczna złożona z zestawu punktów lub wierzchołków oraz zestawu łączników lub krawędzi. Krawędzie łączą wierzchołki i te wierzchołki są skierowane. Również żadne cykle lub innymi słowy skierowana krawędź łącząca wierzchołek z wierzchołkiem nie są dozwolone.

5
Pozytywne uporządkowanie topologiczne
Załóżmy, że mam ukierunkowany wykres acykliczny z wagami liczb rzeczywistych na jego wierzchołkach. Chcę znaleźć uporządkowanie topologiczne DAG, w którym dla każdego prefiksu uporządkowania topologicznego suma wag jest nieujemna. Lub jeśli wolisz terminologię teoretyczną, mam ważoną częściową kolejność i chcę liniowego rozszerzenia, aby każdy prefiks miał nieujemną wagę. Co wiadomo …
3
Biorąc pod uwagę ważony Dag, czy istnieje algorytm O (V + E), który zastępuje każdą wagę sumą wag przodka?
Problemem jest oczywiście podwójne liczenie. Jest to dość łatwe dla niektórych klas DAG = drzewo, a nawet drzewo szeregowo-równoległe. Jedynym algorytmem, który znalazłem, który działa na ogólnych DAG w rozsądnym czasie, jest przybliżony (dyfuzja streszczenia), ale zwiększenie jego precyzji jest wykładnicze pod względem liczby bitów (i potrzebuję dużo bitów). Tło: …
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
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
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
Jak drogie może być zniszczenie wszystkich długich ścieżek w DAG?
Uważamy DAG (skierowane wykresy acykliczne) z jednym węzłem źródłowym jeden docelowego węzła ; dozwolone są równoległe krawędzie łączące tę samą parę wierzchołków. - cięcie jest zestaw krawędzi, których usunięcie usunięcie wszystkich - ścieżek dłuższe niż ; krótsze - szlaki, a także wydłużone „wewnętrzny” (te, które nie ścieżki pomiędzy i ), …
1
Dokładny algorytm dla problemu znakowania krawędzi w DAG
Wdrażam część systemu, która wymaga pomocy. Dlatego kadruję go jako problem graficzny, aby uczynić go niezależnym od domeny. Problem: Otrzymujemy ukierunkowany wykres acykliczny . Bez utraty ogólności załóżmy, że G ma dokładnie jeden wierzchołek źródłowy s i dokładnie jeden wierzchołek tonący ; pozwolić P oznacza zbiór wszystkich skierowanych ścieżek z …
2
Leksykograficznie minimalny rodzaj topologiczny oznaczonego DAG
Rozważmy problem, w którym jako dane wejściowe podajemy ukierunkowany wykres acykliczny , funkcję znakowania λ od V do jakiegoś zbioru L o całkowitej kolejności < L (np. Liczby całkowite) i gdzie jesteśmy proszeni o obliczyć leksykograficznie najmniejszy rodzaj topologiczny G pod względem λ . Dokładniej, A topologiczna sortowania z G …
4
Skierowane trudne NP problemy na DAG
Szerokość drzewa mierzy, jak blisko wykresu znajduje się drzewo. Kilka problemów trudnych dla NP można rozwiązać na wykresach z ograniczoną szerokością drzewa. Jeśli na drzewach nadal występuje trudny NP, szerokość drzewa nie może nas uratować. Taka była motywacja jednego z moich wcześniejszych pytań, które dotyczyły trudnych NP problemów na drzewach. …
1
Pozytywne uporządkowanie topologiczne, weź 2
Jest to kontynuacja ostatniego pytania Davida Eppsteina i jest motywowana tymi samymi problemami. Załóżmy, że mam wierzchołek z ciężarami na liczbach rzeczywistych na jego wierzchołkach. Początkowo wszystkie wierzchołki są nieoznaczone. Mogę zmienić zestaw zaznaczonych wierzchołków, albo (1) zaznaczając wierzchołek bez nieoznaczonych poprzedników, albo (2) odznaczając wierzchołek bez zaznaczonych następców. (Zatem …
3
Wydajne porównanie DAG przez sieć
W rozproszonych systemach kontroli wersji (takich jak Mercurial i Git ) istnieje potrzeba skutecznego porównywania ukierunkowanych wykresów acyklicznych (DAG). Jestem programistą Mercurial i bardzo chcielibyśmy usłyszeć o pracy teoretycznej, która omawia złożoność czasową i sieciową porównywania dwóch DAG. Wspomniane DAG są tworzone na podstawie zarejestrowanych zmian. Wersje są jednoznacznie identyfikowane …
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.