Wiemy, że maksymalny niezależny zestaw (MIS) jest trudny do przybliżenia przy współczynniku dla dowolnego ϵ > 0, chyba że P = NP. Jakie są specjalne klasy wykresów, dla których znane są lepsze algorytmy aproksymacyjne?n1−ϵn1−ϵn^{1-\epsilon}ϵ>0ϵ>0\epsilon > 0 Jakie są wykresy, dla których...
wszyscy wiedzą, że istnieje wiele problemów decyzyjnych, które są trudne NP na ogólnych wykresach, ale interesują mnie problemy, które są trudne NP, gdy podstawowy wykres jest ścieżką. Czy możesz mi pomóc w zebraniu takich problemów? Znalazłem już powiązane pytanie dotyczące trudnych NP problemów...
Szukam nieukierunkowanych, nieważonych połączonych wykresów , w których dla każdej pary u , v ∈ V istnieje unikalna ścieżka u → v, która realizuje odległość d ( u , v ) .G = ( V, E)sol=(V.,mi)G=(V,E)u , v ∈ V.u,v∈V.u,v \in Vu → vu→vu \rightarrow vre( u , v )re(u,v)d(u,v) Czy ta klasa grafów jest...
Czy ktoś wie o otwartym oprogramowaniu do obliczania rozkładu drzewa grafów dla ustalonej „k” (szerokość)? Wiem, że problem ze znalezieniem rozkładu drzewa jest trudny NP dla zmiennej „k”, ale moje instancje wejściowe będą naprawdę małe (~ 10 węzłów), a „k” jest...
Rozważam klasy grafów, które można scharakteryzować za pomocą zabronionych subgrafów. Jeśli klasa grafów ma skończony zestaw zabronionych podgraphów, wówczas istnieje trywialny algorytm wielomianowego rozpoznawania czasu (można po prostu użyć brutalnej siły). Ale nieskończona rodzina zakazanych...
Jakie aplikacje mają problemy z wierzchołkiem w prawdziwym świecie? Które projekty branżowe lub badawcze wykorzystują faktycznie zaimplementowane oprogramowanie oparte na teoretycznych wynikach problemu dotyczącego Vertex Cover? W szczególności, czy któryś z poniższych wyników teoretycznych jest...
Jakie są podstawowe odniesienia? Czy są jakieś dobre, wysokopoziomowe ankiety dotyczące SGT i jego zastosowań w CS w ogóle, a bardziej konkretnie w uczeniu
Czas dojazdu na połączonym wykresie definiuje się jako oczekiwaną liczbę kroków w losowym marszu rozpoczynającym się od , przed odwiedzeniem węzła a następnie ponownie osiągnięciem węzła . Jest to w zasadzie suma dwóch czasów uderzenia i .i j i H ( i , j ) H ( j , i...
Rozważmy sieć elektryczną zamodelowaną jako płaski wykres G, gdzie każda krawędź reprezentuje rezystor 1 Ω. Jak szybko możemy obliczyć dokładną efektywną rezystancję między dwoma wierzchołkami w G? Równolegle, jak szybko możemy obliczyć dokładny prąd płynący wzdłuż każdej krawędzi, jeśli podłączymy...
Wykresy sześcienne to wykresy, w których każdy wierzchołek ma stopień 3. Zostały one szeroko zbadane i jestem świadomy, że kilka problemów trudnych dla NP pozostaje trudnych dla NP nawet ograniczonych do podklas grafów sześciennych, ale niektóre inne stają się łatwiejsze. Nadklasą wykresów...
W grze typu tower defense masz siatkę NxM z początkiem, wykończeniem i wieloma ścianami. Wrogowie podążają najkrótszą ścieżką od początku do końca, nie przechodząc przez ściany (zwykle nie są ograniczeni do siatki, ale dla uproszczenia powiedzmy, że są. W obu przypadkach nie mogą poruszać się po...
1- Czy są jakieś szczególne właściwości macierzy przylegania, gdy wykres jest płaski? 2- Czy jest coś specjalnego do obliczania stałej macierzy przylegania, gdy wykres jest
(crossposted z MathOverflow) Cześć, Czytałem ten wątek: /mathpro/16393/finding-a-cycle-of-fixed-length Chcę znaleźć 5-cykl na wykresie. Tak naprawdę to, czego naprawdę chcę, to najkrótszy nieparzysty cykl o długości co najmniej 5, ale może to trochę poza tym. Dla moich celów, traktuję i to samo...
Rozważając nieco to pytanie , próbowałem zidentyfikować wszystkie różne powody, dla których wykres może nie być k kolorowy. Są to jedyne 2 powody, które udało mi się dotychczas zidentyfikować:G=(VG,EG)G=(VG,EG)G = (V_G,E_G)kkk zawiera klikę o rozmiarze k + 1 . To oczywisty...
Rozważ zestaw płaskich wykresów, w których wszystkie ściany wewnętrzne są trójkątami. Jeśli jest punkt wewnętrzny nieparzystego stopnia, wykres nie może być trójkolorowy. Jeśli każdy punkt wewnętrzny ma równy stopień, czy zawsze może być trójkolorowy? Idealnie chciałbym mały...
Tło: Niech będą dwoma wierzchołkami niekierowanego wykresu G = ( V , E ) . Zestaw wierzchołek S ⊆ V jest U , V -separator jeżeli U i V , należą do różnych połączonych składników G - S . Jeśli żaden odpowiedni podzbiór separatora u , v S nie jest separatorem u , v, wówczas S jest minimalnym u , vu...
Pazur to . Trywialny algorytm wykryje pazur w czasie . Można to zrobić w , gdzie jest wykładnikiem szybkiego mnożenia macierzy, w następujący sposób: weź podrozdział wywołany przez dla każdego wierzchołka i znajdź trójkąt w jego uzupełnienie. O ( n 4 ) O ( n ω + 1 ) ω N [ v ]...
W moich badaniach pojawił się ostatnio następujący interesujący problem: INSTANCJA: Wykres .G ( V, E)G(V,E)G(V, E) ROZWIĄZANIE: Zakończenie akordu nieparzystego cyklu nieparzystego, zdefiniowane jako nadzbiór zestawu krawędzi tak że skompletowany wykres ma właściwość polegającą na tym, że każda...
Właśnie przeczytałem na niemieckiej Wikipedii, że nieskończony wykres to wykres z nieskończoną liczbą węzłów lub nieskończoną liczbą krawędzi. Znam tylko aplikacje i algorytmy dla grafów skończonych. Do czego służą wykresy nieskończone? Jakie są ich zastosowania? Nie wyobrażam sobie algorytmów,...
Klasę złożoności PPAD (np. Obliczanie różnych równowag Nasha) można zdefiniować jako zbiór całkowitych problemów z wyszukiwaniem, które można zredukować do ZAKOŃCZENIA LINII : KONIEC LINII : Biorąc pod uwagę obwody S i P z n bitami wejściowymi i n bitami wyjściowymi takimi, że P (0 n ) = 0 n ! = S...