Pytania otagowane jako graph-algorithms

Algorytmy na wykresach, z wyłączeniem heurystyki.

2
„Krewni” problemu najkrótszej ścieżki
Rozważ dołączony niekierowany wykres z nieujemnymi wagami krawędzi i dwoma wyróżnionymi wierzchołkami . Poniżej przedstawiono niektóre problemy ze ścieżką, które mają następującą postać: znajdź ścieżkę , tak aby jakaś funkcja ciężaru krawędzi na ścieżce była minimalna. W tym sensie wszyscy są „krewnymi” problemu najkrótszej ścieżki; w tym ostatnim funkcja jest …
3
Problem najkrótszej odległości z długością jako funkcją czasu
Motywacja Pewnego dnia podróżowałem po mieście środkami transportu publicznego i stworzyłem interesujący problem graficzny, modelujący problem znalezienia najkrótszego połączenia między dwoma miejscami. Wszyscy znamy klasyczny „problem najkrótszej ścieżki”: biorąc pod uwagę ukierunkowany wykres o długości krawędzi i dwóch wierzchołkach , znalezienie najkrótszej ścieżki pomiędzy i (to znaczy ścieżka minimalizację całkowitej …
2
Losowy spacer i średni czas trafienia na prostym niekierowanym wykresie
Niech będzie prostym nieukierowanym wykresem na wierzchołkach i krawędziach.n mG=(V,E)sol=(V.,mi)G=(V,E)nnnmmm Próbuję określić czas oczekiwany prowadzeniem algorytmu Wilsona do generowania losowych rozpinające drzewo . Tam pokazano, że to , gdzie to średni czas uderzenia : gdzie:O ( τ ) τGsolGO(τ)O(τ)O(\tau)ττ\tauτ=∑v∈Vπ(v)⋅H(u,v),τ=∑v∈V.π(v)⋅H.(u,v),\tau = \sum_{v \in V} \pi(v) \cdot H(u, v), ππ\pi to rozkład …
0
Prosta ścieżka na sztyfcie z tylnymi krawędziami
Jaka jest złożoność następującego problemu ( P? NP-trudny?):∈∈\in Dane wejściowe: ukierunkowany wykres acykliczny , zestaw tylnych krawędzi E ′ ⊂ V × V i dwa odrębne węzły sD=(V,E)D=(V,E)D=(V,E)E′⊂V×VE′⊂V×VE'\subset V\times Vsss i .ttt Pytanie: Niech oznacza wykres utworzony przez dodanie do D krawędzi od E ′ . Czy istnieje prosta ścieżka …
2
Które problemy z grafem są trudne dla na wykresach skierowanych (/ ważonych), ale FPT na wykresach niekierowanych (/ nieważonych)?
Po równoważnych pytaniach dotyczących kompletności NP (patrz pytanie wagi i pytanie kierowane ) zastanawiałem się, w jaki sposób atrybuty te wpływają na sparametryzowane problemy. Które problemy z twardym grafem są trudne dla na grafach ukierunkowanych, ale stały parametr można traktować na grafach bezkierunkowych?NPNPNPW[1]W[1]W[1] Które problemy z twardym grafem są trudne …
2
Kompletność obejmująca drzewa
Drzewo opinające wykresu nazywane jest drzewem kompletności, jeśli zbiór jego liści indukuje całkowity podrozdział na grafie gospodarza. Biorąc pod uwagę wykres i liczbę całkowitą , jaka jest złożoność decyzji, czy zawiera drzewo kompletności z co najwyżej liści?GsolGkkkGGGkkk Powodem zadawania tego pytania jest to, że odpowiadającym problemem dla drzew niezależności jest …
1
Znajdowanie ścieżek rozłącznych wierzchołków od minimum do maksimum ze wspólnym źródłem na wykresach planarnych
Biorąc pod uwagę płaski wykres nieważony i zbiór par wierzchołków ( k ≥ 2 jest stałą), znajdź k ścieżek rozłącznych wierzchołków (z wyjątkiem źródła) od s do t i tak, że długość najdłuższej ścieżki jest zminimalizowana.( s , t1) , … , ( S , tk)(s,t1),…,(s,tk)(s,t_1),\dots,(s,t_k)k ≥ 2k≥2k\ge2kkkssstjatit_i Pytanie: Czy …
1
Łączenie komórek za pomocą permutacji liniowych i kolumnowych w skończonej siatce
Chciałbym wiedzieć, czy wcześniej zbadano następujący prosty problem i czy znane jest jakieś rozwiązanie. Niech G będzie siatką skończoną (MxN), S podzbiorem komórek G („okruchy”). Mówi się, że dwie okruchy są (lokalnie) połączone, jeśli ich współrzędne różnią się co najwyżej o jeden (tj. Jeśli narysowane jako kwadraty, dzielą co najmniej …
2
Sortowanie punktów, aby zminimalizować minimalną odległość euklidesową między kolejnymi punktami
Biorąc pod uwagę zestaw punktów w trójwymiarowej przestrzeni kartezjańskiej, szukam algorytmu, który posortuje te punkty, tak aby zminimalizować minimalną odległość euklidesową między dwoma kolejnymi punktami. Byłoby również korzystne, gdyby algorytm miał tendencję do wyższej średniej odległości euklidesowej między kolejnymi punktami.
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.