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...
Wykonaj ukierunkowany wykres gdzie krawędzie są ozdobione naturalną liczbą. Chcemy zestawu wszystkich ścieżek między dwoma wierzchołkami v 1 i tak aby każda kolejna krawędź ścieżki była ozdobiona liczbą naturalną, która jest większa niż liczba naturalna dekorująca poprzednią krawędź.GGGv...
Biorąc pod uwagę prosty niekierowany wykres GGG , znajdź podzbiór A≠∅A≠∅A\neq \emptyset wierzchołków, taki jak dla dowolnego wierzchołka x∈Ax∈Ax\in A co najmniej połowa sąsiadów xxx również znajduje się w AAA i rozmiar AAA jest minimalny. Oznacza to, że szukamy gromady, w której co najmniej...
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...
Klasycznym rozszerzeniem problemu maksymalnego przepływu jest problem „maksymalnego przepływu w czasie”: otrzymujesz wykrój, którego dwa węzły są rozróżniane jako źródło i zlew, przy czym każdy łuk ma dwa parametry, wydajność na czas i opóźnienie. Jesteś również biorąc pod uwagę horyzont czasowy ....
Mniej więcej rok temu razem z przyjacielem zastanawialiśmy się, jak zaimplementować algorytm Kruskala dla gęstych wykresów w lepszej niż zwykle granicy O ( m logm )O(mlogm)O(m \log m) (bez zakładania wstępnie posortowanych krawędzi). Konkretnie, osiągamy Θ ( n2))Θ(n2))\Theta(n^2) we wszystkich...
∑x∏i j ∈ Efa( xja, xjot)∑x∏jajot∈mifa(xja,xjot)\sum_x \prod_{ij \in E} f(x_i,x_j)maxx∏i j ∈ Efa( xja, xjot)maxx∏jajot∈mifa(xja,xjot)\max_x \prod_{ij \in E} f(x_i,x_j) Gdzie Max lub suma przejmuje wszystkie labelings z , produkt wprowadza się na wszystkie krawędzie dla grafu G = \ {V, E \} i f jest...
W prostej formie: Można dwukierunkowa skończony automat rozpoznaje vvv wykresy -Vertex które zawierają trójkąt z o(v3)o(v3)o(v^3) stany? Detale Zainteresowania są tu vvv wykresy -Vertex kodowane przy użyciu sekwencji krawędzi, każda krawędź jest para różnych wierzchołki...
Próbuję zrozumieć niektóre pojęcia dotyczące rozkładu modułowego i wykresów szerokości kliki . W tym artykule („Na wykresach uporządkowanych za pomocą P4”) znajduje się dowód na to, jak rozwiązać problemy z optymalizacją, takie jak liczba kliki lub liczba chromatyczna za pomocą rozkładu...
Problem z rowem jest następujący:kkk Instancja: Niekierowany wykres z wierzchołkami i do n \ wybierz 2 krawędzie.nsolsolGnnn( n2))(n2))n \choose 2 Pytanie: Czy w G istnieje (właściwy) cykl K ?kkksolsolG Tło: Dla każdego ustalonego kkk możemy rozwiązać cykl 2 tys2)k2k w czasie O (...
Jakie są dobre artykuły / książki, aby lepiej zrozumieć moc rozkładu modułowego i jego właściwości? Szczególnie interesują mnie algorytmiczne aspekty dekompozycji modułowej. Słyszałem, że można znaleźć rozkład modułowy wykresu w czasie liniowym. Czy istnieje do tego stosunkowo prosty algorytm? Co...
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...
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 ;...
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...
Wykazano, że propagacja przekonań jest bardzo skuteczną metodą dzięki badaniom w probabilistycznych modelach graficznych. Jednak nie wiem nic o BP, które byłoby porównywalne z metodami MCMC, w których możemy mieć w pełni wielomianowe losowe schematy aproksymacji (FPRAS) dla problemów z #...
Najdłuższy problem ze ścieżką to trudność NP. (Typowy?) Dowód polega na zmniejszeniu problemu ścieżki hamiltonowskiej (która jest NP-zupełna). Zauważ, że tutaj ścieżka jest uważana za (węzłową) prostą. Oznacza to, że żaden wierzchołek nie może wystąpić więcej niż jeden raz na ścieżce. Oczywiście...
Biorąc pod uwagę wykres, G=(V,E)G=(V,E)G = (V, E) , to znaleźć optymalną rrr -domination dla GGG . Oznacza to, że chce podzbiór SSS o VVV tak, że wszystkie wierzchołki GGG znajdują się w odległości co najwyżej rrr z pewnym wierzchołka w SSS , przy jednoczesnym zminimalizowaniu rozmiaru .SSS Z...
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...
Jaka jest złożoność następującego problemu? Wejście : aścieżka hamiltonowskaw K nHH.HKnKnK_n podzbiór par wierzchołkówR⊆[n]2R⊆[n]2R \subseteq [n]^2 dodatnia liczba całkowita kkk Pytanie : czy istnieje pasujące , że dla każdego ( v , u ) ∈ R , d G ( v , u ) ≤ k ? (gdzie G = ( [ n ] , M ∪ H )...
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...