Teoretyczne informatyka graph-theory

1

Następujące pytanie jest związane z optymalności Bellmana-Forda - najkrótsza droga algorytm programowania dynamicznego (patrz ten post dla połączenia). Pozytywna odpowiedź sugerowałaby również, że minimalny rozmiar monotonicznego niedeterministycznego programu do rozgałęziania dla problemu STCONN to . tssstttΘ(n3)Θ(n3)\Theta(n^3) Niech być DAG (skierowane acykliczny wykres) z jednym węzłem źródłowym jeden docelowego węzła . …

10 graph-theory circuit-complexity lower-bounds

1

Generowanie wykresów obwodu

Niech . Muszę wygenerować proste wykresy obwodu tak aby zestaw wszystkich motocykli tworzy podwójną osłonę (to znaczy, każda krawędź jest dzielona przez dokładnie dwa motocykle) i takie, że przecięcie dowolnych dwóch motocykle to albo wierzchołek, krawędź, albo pusty. Wygenerowane wykresy powinny być dowolnie duże.G g g G g gsol≥ 3g≥3g\geq …

10 ds.algorithms reference-request graph-theory co.combinatorics pseudorandom-generators

1

Algorytmy na wykresach reprezentowane za pomocą BDD

Najprostsze reprezentacje wykresów wykorzystują macierze / listy przyległości, co oznacza, że każdy węzeł i krawędź są wyraźnie reprezentowane. Znaczenie ukrytych reprezentacji dla wykresów wykazujących silne prawidłowości od dawna zostało uznane. Na przykład Galperin i Wigderson (1983), Papadimitriou i Yannakakis ( Nota o zwięzłych reprezentacjach grafów , 1986) badali kwestię wykresów, …

10 ds.algorithms reference-request graph-theory survey binary-decision-diagrams

2

Decydujący homomorfizm grafowy

Graf decydujący Homomorfizm jest ogólnie NP-Complete. Czy istnieją wyniki, które badają ten problem, gdy leżące u podstaw wykresy mają strukturę algebraiczną (takie jak decydowanie o homomorfizmach z wykresów Coseleya lub Cayleya do innych wykresów o określonej strukturze również)? Oprócz wyników złożoności interesują mnie również pomocne techniki algebraiczne i / lub …

10 cc.complexity-theory graph-theory co.combinatorics

1

Czym jest algorytm znajdujący minimalną osłonę wierzchołków na dwustronnym grafie z ważonymi wierzchołkami?

Wiem, że dla nieważonego grafu dwustronnego mogę znaleźć minimalną osłonę wierzchołków, najpierw znajdując maksymalne dopasowanie i przekształcając ją w osłonę wierzchołków za pomocą Twierdzenia Königa. Czy istnieje modyfikacja, której można by użyć, gdyby węzły były ważone?

10 ds.algorithms graph-theory

1

Problem decyzyjny rozkładu Hamiltona

Niech będzie wykresem niekierowanym. Rozkładem V na podzbiory rozłączne V i nazywa się Hamilton rozkładu z G jeśli subgraph wywołanych przez każdy zestaw V i jest albo wykres Hamiltona lub składa się z jednej krawędzi z | V i | = 2 .G = ( V, E)sol=(V.,mi)G=(V,E)V.V.VV.jaV.jaV_isolsolGV.jaV.jaV_i| V.ja| =2|V.ja|=2)|V_i|=2 Przykład …

10 cc.complexity-theory ds.algorithms graph-theory np-hardness hamiltonian-paths

2

Amplituda losowych wykresów sześciennych

Rozważ dołączony losowy wykres sześcienny G=(V,E)G=(V,E)G=(V,E) z n=|V|n=|V|n =|V|wierzchołki narysowane z G(n,3G(n,3G(n, 3 reg ))) (jak tu zdefiniowano , tzn. 3n3n3n jest parzyste, a dowolne dwa wykresy mają takie samo prawdopodobieństwo). Oczywiście istnieje nnn możliwe Szerokość najpierw szuka, po jednej dla każdego węzła wyjściowych s∈Vs∈Vs \in V . Przeszukiwanie wszerz …

10 graph-theory co.combinatorics

1

Schemat Voronoi na wykresie

Niech będzie wykresem z (dodatnio) ważonymi krawędziami. I chcemy określić schemat Voronoi dla zestawu węzłów / miejsca , do wiązania się z węzła subgraph w indukowanej przez wszystkie węzły ściśle bliżej niż jakiegokolwiek innego węzła , pomiar długości ścieżki za pomocą sumy wag na łukach. jest „s Woronoja obszar . …

10 reference-request graph-theory cg.comp-geom

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 …

10 ds.algorithms graph-theory graph-algorithms

1

Zwykły wykres wysokiego obwodu z „lokalnie jednolitym” całkowitym porządkiem w węzłach

Definicje Niech i niech d , r i g będą dodatnimi liczbami całkowitymi (z g > 2 r + 1 ).ϵ>0ϵ>0\epsilon > 0dddrrrgggg>2r+1g>2r+1g > 2r+1 Niech są proste, d -regular, nieukierunkowane skończonej wykres z obwodu co najmniej g .G=(V,E)G=(V,E)G = (V,E)dddggg Niech być całkowity porządek na V .≤≤\leVVV Dla każdego …

10 graph-theory co.combinatorics dc.distributed-comp

1

Twardość przybliżonej ułamkowej liczby chromatycznej na wykresach ze stopniem granicznym

Czy trudno jest apx-przybliżać ułamkową liczbę chromatyczną na wykresach ze stopniem granicznym?

10 cc.complexity-theory graph-theory approximation-hardness graph-colouring bounded-degree

1

Czy taka matryca może istnieć?

Podczas mojej pracy wpadłem na następujący problem: Usiłuję znaleźć macierz n × nn×nn \times n M dla dowolnego n > 3 o następujących właściwościach:( 0 , 1 )(0,1)(0,1)M.M.Mn > 3n>3)n > 3 Wyznacznik M.M.M jest parzysty. Dla niepustych podzbiorów ja, J⊆ { 1 , 2 , 3 }ja,jot⊆{1,2),3)}I,J\subseteq\{1,2,3\} z | …

10 graph-theory co.combinatorics linear-algebra matrices boolean-matrix

1

Znalezienie rozpinających się pająków

Czy istnieje algorytm wielomianowy do znalezienia - jeśli taki istnieje - pająka rozpinającego danego wykresu ? Pająk to drzewo z co najmniej jednym węzłem o stopniu większym niż 2: Wiem, że różne warunki stopnia na (zasadniczo wystarczająco duże stopnie węzła) gwarantują istnienie pająka rozpinającego. Ale zastanawiam się, czy istnieje algorytm …

10 ds.algorithms reference-request graph-theory graph-algorithms

2

Kiedy właściwość FO zabija twardość NL?

Kontekst: Rozważamy tylko digrafy. Niech CYKL będzie językiem grafów z cyklem; jest to problem kompletny dla NL. Niech HASEDGE będzie językiem grafów z co najmniej jedną krawędzią. Zatem w sposób trywialny nie jest już trudny dla NL, podczas gdy zostaje.CYCLE∪HASEDGECYCLE∪HASEDGE\text{CYCLE} \cup \text{HASEDGE}CYCLE∪HASEDGE¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯CYCLE∪HASEDGE¯\text{CYCLE} \cup \overline{\text{HASEDGE}} Rzeczywisty problem: zastanawiam się, czy język …

10 cc.complexity-theory graph-theory descriptive-complexity

4

Liczba klików na wykresie: wynik Księżyca i Mosera 1965

Szukam pełnego tekstu wyniku kliknięcia Księżyca i Mosera z 1965 r. O klikach na wykresach (istnieją wykresy z liczbą maksymalnych wykładniczych klik w ). Zapora mojego uniwersytetu nie ma dostępu do konkretnego czasopisma. (W rzeczywistości podgląd zawiera kilka pierwszych zdań dowodu, ale potem pozostawia mnie bez reszty!)nnn Byłem zainteresowany tym …

10 reference-request graph-theory co.combinatorics clique

Pytania otagowane jako graph-theory