Teoretyczne informatyka graph-isomorphism

1

Czy izomorfizm grafów występuje w UP coUP?

Czy izomorfizm grafów (problem decyzyjny) znajduje się w ? Tutaj to klasa problemów decyzyjnych akceptowanych przez jednoznaczną maszynę Turinga (patrz zoo złożoności ).UP∩coUPUP∩coUP\mathsf{UP}\cap \mathsf{coUP}UPUP\mathsf{UP}

10 cc.complexity-theory graph-isomorphism

1

Czy istnieje algorytm wielomianowy do rozwiązywania izomorfizmu grafów dla grafów Delaunaya (skończonych) heksagonalnych teselacji?

Biorąc pod uwagę skończoną płaszczyznę, mam sześciokątną teselację tej płaszczyzny z regularnym sześciokątem o stałej wielkości. Następnie obliczam wykres G Delaunaya dla teselacji. Biorąc pod uwagę taki wykres G, usuwam określone zestawy węzłów na tym wykresie, aby uzyskać wiele podgraphów G. Muszę ustalić, czy podgrupy te są izomorficzne (względem siebie). …

10 ds.algorithms graph-algorithms graph-isomorphism

2

Liczba automorfizmów wykresu dla izomorfizmu grafowego

Niech i będą dwoma połączonymi wykresami regularnymi o rozmiarze . Niech być zbiorem permutacji tak, że . Jeśli następnie jest zestaw automorfizmy o .GGGHHHrrrnnnAAAPPPPGP−1=HPGP−1=HPGP^{-1}=HG=HG=HG=HAAAGGG Jaka jest najbardziej znana górna granica rozmiaru ? Czy są jakieś wyniki dla poszczególnych klas grafów (niezawierających grafów kompletnych / cyklicznych)?AAA Uwaga: Skonstruowanie grupy automorfizmów jest …

9 reference-request graph-theory co.combinatorics graph-isomorphism gr.group-theory

2

Wykres izomorfizm z relacją równoważności na zbiorze wierzchołków

Kolorowy wykres można opisać jako krotkę (G,c)(G,c)(G,c)gdzie jest wykresem, a jest kolorem. Mówi się, że dwa kolorowe wykresy i są izomorficzne, jeśli istnieje izomorfizm prawy tak, że przestrzegane jest zabarwienie, tj. dla wszystkich .GGGc:V(G)→Nc:V(G)→Nc : V(G) \rightarrow \mathbb{N}(G,c)(G,c)(G,c)(H,d)(H,d)(H,d)π:V(G)→V(H)π:V(G)→V(H)\pi : V(G) \rightarrow V(H)c(v)=d(π(v))c(v)=d(π(v))c(v) = d(\pi(v))v∈V(G)v∈V(G)v \in V(G) Pojęcie to oddaje izomorfizm …

9 terminology graph-isomorphism equivalence

2

Najszybszy znany algorytm deterministyczny dla problemu niekierowanego graficznego izomorfizmu

Jaki jest najszybszy znany algorytm izomorfizmu grafów bezkierunkowych?

9 cc.complexity-theory reference-request graph-algorithms graph-isomorphism

1

Złożoność liczenia endomorfizmów grafowych

Homomorfizm z wykresuG=(V,E)G=(V,E)G = (V, E)na wykresie jest odwzorowaniem od do taki sposób, że jeśli i są obok siebie w czym i sąsiadują z . Endomorfizm grafu jest homomorfizmem od do siebie; nie ma ustalonego punktu, jeśli nie ma takiego, że i nie jest trywialne, jeśli nie jest to tożsamość.G′=(V′,E′)G′=(V′,E′)G' …

9 cc.complexity-theory graph-algorithms counting-complexity graph-isomorphism homomorphism

2

Wydajne algorytmy przeszukiwania kolekcji drzew

Mam duży zestaw danych o drzewach i chciałbym je przeszukać, określając treelet (połączony podgrupa). Kwerenda powinna zwrócić wszystkie wystąpienia treeline w zbiorze danych. Czy istnieją wydajne algorytmy do tego celu? Myślałem o czymś takim jak tablice sufiksów, jednak naiwne kodowanie drzew, ponieważ łańcuchy (przez ustaloną kolejność ich węzłów) nie będą …

9 graph-algorithms ds.data-structures tree graph-isomorphism string-search

Pytania otagowane jako graph-isomorphism