Pytania otagowane jako graph-isomorphism

Dwa wykresy G, H są izomorficzne, jeśli istnieje znakowanie wierzchołków G, które wytwarza H, i odwrotnie. Graficzny problem izomorfizmu (GI) ma decydować, czy dwa podane są izomorficzne. Oprócz praktycznego zainteresowania, Karp w 1972 r. Stwierdził, że ma nieznaną złożoność, jest jednym z niewielu naturalnych kandydatów na problem pośredni NP i doprowadził do powstania klasy złożoności AM.

1
Złożoność testowania, jeśli dwa zestawy
Wyobraźmy sobie, że mamy dwa zestawy rozmiarów punktów . Jaka jest (czasowa) złożoność testowania, jeśli różnią się one tylko rotacją? : istnieje macierz rotacji taka, że ?mmmX,Y⊂RnX,Y⊂RnX,Y\subset \mathbb{R}^nOOT=OTO=IOOT=OTO=IOO^T=O^TO=IX=OYX=OYX=OY Istnieje tutaj problem reprezentowania rzeczywistych wartości - dla uproszczenia załóżmy, że dla każdej współrzędnej istnieje (krótki) wzór algebraiczny, tak że koszt podstawowych …
1
Negatywne wyniki w podejściu identycznych cząstek do problemu Isomorphism Graph (GI)
Podjęto próby zaatakowania problemu izomorfizmu grafów za pomocą kwantowego losowego chodzenia twardych rdzeni (symetryczne, ale bez podwójnego zajęcia). Symetryczna moc matrycy przylegania, która wydawała się obiecująca, wykazano jako niekompletne ogólnych wykresów na tym papierze Amir Rahnamai Barghi i Ilia Ponomarenko. Inne podobne podejście zostało również obalone w tym artykule przez …
1
Na wykresie Izomorfizm Kompletne problemy
Jestem zainteresowany badaniem kompletnych problemów z Graph Isomorphism (GI). W artykule „Problemy wielomianowo równoważne z izomorfizmem grafowym” Kellogga S. Bootha (1979) udowodnili, że wiele podstawowych problemów jest uzupełnionych GI przy użyciu technik zastępowania krawędzi, technik kompozycji itp. Chciałbym nauczyć się kilku innych technik, które są używane w ostatnich artykułach. Czy …
1
Redundancja i struktura problemów obliczeniowych
Powszechnie uważa się, że niektóre problemy obliczeniowe, takie jak izomorfizm grafów, nie mogą być NP-kompletne, ponieważ nie mają wystarczającej struktury lub redundancji, aby były trudne obliczeniowo (NP-twarde). Interesują mnie różne pojęcia formalne dotyczące struktury problemów obliczeniowych i miar redundancji. Jakie są główne znane wyniki takich formalnych pojęć dotyczących problemów obliczeniowych? …
3
Regularne wykresy i izomorfizm
Chciałbym zapytać, czy jest na to już opublikowany wynik: Bierzemy wszystkie możliwe różne ścieżki między każdą parą węzłów dwóch połączonych regularnych (o powiedzmy stopnia , i liczby węzłów ) wykresów i zapisujemy ich długości. Oczywiście ta liczba odrębnych ścieżek ma charakter wykładniczy. Moje pytanie brzmi: jeśli posortujemy długości i porównamy …
1
Czy ktoś zna przeciwny przykład algorytmu grafowego izomorfizmu Dharwadkera-Teveta?
Na stronie http://www.dharwadker.org/tevet/isomorphism/ znajduje się prezentacja algorytmu do określania, czy dwa wykresy są izomorficzne. Biorąc pod uwagę wiele „powiedzmy” interesujących twierdzeń A Dharwadkera, nie jestem skłonny w to uwierzyć. W trakcie mojego dochodzenia stwierdziłem, że algorytm z pewnością da poprawną odpowiedź i powiem, że dwa wykresy nie są izomorficzne, chociaż …
2
Kiedy wielomianowy GI oznacza wielomianowy (krawędziowy) GI?
Skrzyżowane z MO . Izomorfizm kolorowego wykresu (krawędzi) to GI, który zachowuje kolory (krawędzi, jeśli jest w kolorze krawędzi). Istnieje kilka obniżek przy użyciu transformacji / gadżetów GI (krawędzi) w kolorze do GI. W przypadku GI w kolorze krawędzi najprostsze jest zastąpienie kolorowej krawędzi gadżetem chroniącym GI kodującym kolor (najłatwiejszym …
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.