Teoretyczne informatyka graph-algorithms

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 …

14 ds.algorithms reference-request co.combinatorics graph-algorithms directed-acyclic-graph

2

Istnienie płaskiego zabezpieczenia odległości?

Niech G będzie n-węzłem niekierowanym grafem, a niech T będzie podzbiorem węzłów V (G) zwanym zaciskami . Zabezpieczenie odległości (G, T) jest wykresem H spełniającym tę właściwość reH.( u , v ) = dsol( u , v )reH.(u,v)=resol(u,v)d_H(u,v) = d_G(u,v) dla wszystkich węzłów u, v w T. (Należy zauważyć, że …

14 ds.algorithms reference-request graph-algorithms planar-graphs

2

Uogólnienie węgierskiego algorytmu na ogólne niekierowane wykresy?

Algorytm węgierski jest kombinatorycznym algorytmem optymalizacyjnym, który rozwiązuje problem dwustronnego dopasowania maksymalnej masy w czasie wielomianowym i przewidywał późniejszy rozwój ważnej metody pierwotnej podwójnej . Algorytm został opracowany i opublikowany przez Harolda Kuhna w 1955 r., Który nadał mu nazwę „algorytm węgierski”, ponieważ algorytm był oparty na wcześniejszych pracach dwóch …

14 graph-theory reference-request graph-algorithms linear-programming primal-dual

2

Liczba minut wykresu bez użycia algorytmu Kargera

Wiemy, że algorytm wycinania Kargera można wykorzystać do udowodnienia (w niekonstruktywny sposób), że maksymalna liczba możliwych skrótów może mieć wykres ( n2))(n2))n \choose 2 . Zastanawiałem się, czy moglibyśmy w jakiś sposób udowodnić tę tożsamość, podając bijectywny (raczej iniekcyjny) dowód z zestawu skrótów do innego zestawu liczności ( n2))(n2))n \choose …

14 ds.algorithms graph-theory co.combinatorics graph-algorithms max-flow-min-cut

1

Jakie są przeszkody w przedłużeniu

Dowód omer Reingold, że daje algorytm USTCON (W U ndirected wykres ze szczególnym wierzchołki s i t są one Con podłączeń z sieciami?) Za pomocą tylko logspace. Podstawową ideą jest zbudowanie wykresu ekspandera z oryginalnego wykresu, a następnie przejście do wykresu ekspandera. Wykres ekspandera jest tworzony przez wielokrotne kwadratowe obliczenie …

13 graph-algorithms nondeterminism expanders logspace

1

Czy suma podzbioru DAG jest przybliżona?

Dana jest skierowany acykliczny wykres o numer przypisany do każdego wierzchołka ( g : V → N ), i docelową liczbą T ∈ N .G=(V,E)G=(V,E)G=(V,E)g:V→Ng:V→Ng:V\to \mathbb{N}T∈NT∈NT\in \mathbb{N} Problem sumy podzbioru DAG (może występować pod inną nazwą, odniesienie będzie wielki) pyta, czy istnieją wierzchołki , tak że Σ V I g …

13 ds.algorithms graph-theory graph-algorithms approximation-algorithms subset-sum

2

Złożoność obliczania najgęstszej nieletniej

Rozważ następujący problem. Dane wejściowe: niekierowany wykres . Dane wyjściowe: wykres H, który jest niewielką wartością G, o najwyższej gęstości krawędzi wśród wszystkich nieletnich G , tj. O najwyższym stosunku | E ( H ) | / | V ( H ) | .G=(V,E)G=(V,E)G=(V,E)HHHGGGGGG|E(H)|/|V(H)||E(H)|/|V(H)||E(H)|/|V(H)| Czy zbadano ten problem? Czy jest …

13 graph-theory graph-algorithms np-hardness graph-minor

1

Złożoność dominującego problemu w określonych podklasach wykresów akordowych

Interesuje mnie złożoność problemu dominującego zestawu (DSP) w niektórych określonych klasach grafów, które są podklasami grafów akordowych . Wykres jest nieukierowanym wykresem ścieżki, jeśli jest to wykres przecięcia wierzchołków rodziny ścieżek w jakimś niekierowanym drzewie. Niech UP będzie klasą niekierowanych grafów ścieżek. Wykres jest grafem EPT, jeśli jest to wykres …

13 reference-request graph-theory graph-algorithms np-hardness

3

Czy ten optymalny problem z podróżą w terminach NP-trudnych na drzewach?

Jeden z moich znajomych pyta mnie o następujący problem z planowaniem na drzewie. Uważam, że jest bardzo czysty i interesujący. Czy jest na to jakieś odniesienie? Problem: Istnieje drzewo , każda krawędź ma symetryczny koszt podróży 1 . Dla każdego wierzchołka v I nie jest to zadanie, które musi być …

13 ds.algorithms graph-algorithms np-hardness

1

Na podstawie wykresu zdecyduj, czy jego łączność brzegowa wynosi co najmniej n / 2, czy nie

Rozdział 1 książki Metoda probabilistyczna autorstwa Alona i Spencera wymienia następujący problem: Biorąc pod uwagę wykres , zdecyduj, czy jego łączność brzegowa wynosi co najmniej czy nie.GGGn/2n/2n/2 Autor wspomina o istnieniu przez Matula algorytmu i ulepsza go do .O(n3)O(n3)O(n^3)O(n8/3logn)O(n8/3log⁡n)O(n^{8/3}\log n) Moje pytanie brzmi: jaki jest najbardziej znany czas wykonywania tego …

13 ds.algorithms open-problem graph-algorithms

3

Wdrożony kod do obliczania szerokości ścieżki (= numer wyszukiwania węzła, numer separacji wierzchołków, grubość przedziału)

Szukam implementacji algorytmu do obliczania szerokości ścieżki wykresu. Dobrze wiadomo, że obliczenie szerokości ścieżki jest równoważne z obliczeniem numeru wyszukiwania węzła, numeru separacji wierzchołków lub grubości przedziału wykresu. Algorytm nie musi być bardzo szybki; Chcę uruchomić go na wykresach o maksymalnie 20 wierzchołkach. Wymagam od algorytmu dokładnego obliczenia szerokości ścieżki, …

13 ds.algorithms reference-request graph-algorithms implementation

1

Największy wspólny podgraf dwóch maksymalnych wykresów płaskich

Rozważ następujący problem - Biorąc pod uwagę maksymalne płaskie wykresy i G 2 , znajdź wykres G z maksymalną liczbą krawędzi, tak że w G 1 i G 2 jest podgraph (niekoniecznie indukowany), który jest izomorficzny do Gsol1G1G_1sol2)G2G_2solGGsol1G1G_1sol2)G2G_2solGG . Czy można to zrobić w czasie wielomianowym? Jeśli tak, to jak? …

13 ds.algorithms graph-algorithms planar-graphs

1

Delikatne wprowadzenie do algorytmicznych aspektów głębokości drzewa

Szerokość i szerokość ścieżki są popularnymi parametrami, mierzącymi odpowiednio bliskość wykresu do drzewa lub ścieżki. Rzeczywiście wydaje się, że szerokość jest tak popularna, że pojawia się w wielu artykułach, książkach i notatkach z wykładów, które dają (nawet bardzo delikatne) wprowadzenie do algorytmicznych aspektów szerokości (patrz np. Książka Downey & Fellows). …

13 reference-request graph-algorithms parameterized-complexity

1

Znalezienie najkrótszej ścieżki w obecności cykli ujemnych

Biorąc pod uwagę ukierunkowany wykres cykliczny, na którym ciężar każdej krawędzi może być ujemny, koncepcja „najkrótszej ścieżki” ma sens tylko wtedy, gdy nie ma żadnych cykli ujemnych, iw takim przypadku można zastosować algorytm Bellmana-Forda. Jestem jednak zainteresowany znalezieniem najkrótszej ścieżki między dwoma wierzchołkami, która nie wymaga cyklizacji (tj. Pod warunkiem, …

13 ds.algorithms graph-algorithms shortest-path

4

Czy problem z ustawieniem wierzchołka sprzężenia zwrotnego na płaskich wykresach stopni jest trudny?

Czy wiadomo, czy problem z ustawieniem wierzchołka sprzężenia zwrotnego na niekierowanych grafach płaskich o ograniczonym stopniu jest twardy?NPNP\mathsf{NP}

13 cc.complexity-theory reference-request graph-algorithms np-hardness

Pytania otagowane jako graph-algorithms