Teoretyczne informatyka graph-theory

5

Moje dzisiejsze pytanie jest (jak zwykle) trochę głupie; ale prosiłbym cię o pomyślne rozważenie. Chciałem wiedzieć o genezie i / lub motywacji leżącej u podstaw koncepcji treewidth. Z pewnością rozumiem, że jest on stosowany w algorytmach FPT, ale nie sądzę, że to był powód, dla którego zdefiniowano to pojęcie. Pisałem …

61 graph-theory co.combinatorics big-picture ho.history-overview treewidth

3

Konsekwencje quasi-wielomianowego algorytmu czasowego dla problemu izomorfizmu grafowego

Problemem wykres Izomorfizm (Gl) jest prawdopodobnie najbardziej znanym kandydatem na NP pośredniego problemu. Najbardziej znanym algorytmem jest algorytm subwykładniczy z czasem działania . Wiadomo, że GI nie jest -kompletny, chyba że hierarchia wielomianowa się załamie.2O(nlogn√)2O(nlog⁡n)2^{O(\sqrt{n \log n})}NPNP\mathsf{NP} Jakie byłyby teoretyczne konsekwencje złożoności quasi-wielomianowego algorytmu czasowego dla problemu grafowego izomorfizmu? Czy …

40 cc.complexity-theory ds.algorithms graph-theory graph-isomorphism

2

Ile różnych kolorów jest potrzebnych, aby ograniczyć możliwości wyboru wykresu?

Wykres jest kkk wyboru (znany również jako kkk -list-colorable ), jeśli dla każdej funkcji fff która odwzorowuje wierzchołki na zestawy kkk kolorów, istnieje przypisanie kolorów ccc tak że dla wszystkich wierzchołków vvv , c(v)∈f(v)c(v)∈f(v)c(v)\in f(v) i takie, że dla wszystkich krawędzi vwvwvw , c(v)≠c(w)c(v)≠c(w)c(v)\ne c(w) . Załóżmy teraz, że wykres …

39 graph-theory co.combinatorics graph-colouring exp-time-algorithms

17

Przypuszczenia sugerujące twierdzenie o czterech kolorach

Twierdzenie o czterech kolorach (4CT) stwierdza, że każdy płaski wykres jest czterokolorowy. Istnieją dwa dowody podane przez [Appel, Haken 1976] i [Robertson, Sanders, Seymour, Thomas 1997]. Oba te dowody są wspierane komputerowo i dość przerażające. Istnieje kilka domysłów w teorii grafów, które sugerują 4CT. Rozwiązanie tych przypuszczeń wymaga prawdopodobnie lepszego …

38 graph-theory co.combinatorics big-list graph-colouring

9

Dane do testowania algorytmów grafowych

Szukam źródła ogromnych zestawów danych do przetestowania implementacji algorytmu grafowego. Proszę również podać informacje o typie / rozkładzie (np. Skierowane / nieukierowane, proste / nie proste, ważone / nieważone) wykresów w źródle, jeśli są one znane.

36 ds.algorithms graph-theory ds.data-structures data-sets

3

Max-cut z ujemnymi krawędziami wagi

G=(V,E,w)G = (V, E, w)w:E→Rw:E\rightarrow \mathbb{R}arg max S ⊂ V ∑ ( u , v ) ∈ E : u ∈ S , v ∉ S w ( u , v ) w ( e ) ≥ 0 e ∈ EargmaxS⊂V∑(u,v)∈E:u∈S,v∉Sw(u,v)\arg\max_{S \subset V} \sum_{(u,v) \in E : u \in S, …

35 ds.algorithms graph-theory approximation-algorithms max-cut

3

Biorąc pod uwagę ważony Dag, czy istnieje algorytm O (V + E), który zastępuje każdą wagę sumą wag przodka?

Problemem jest oczywiście podwójne liczenie. Jest to dość łatwe dla niektórych klas DAG = drzewo, a nawet drzewo szeregowo-równoległe. Jedynym algorytmem, który znalazłem, który działa na ogólnych DAG w rozsądnym czasie, jest przybliżony (dyfuzja streszczenia), ale zwiększenie jego precyzji jest wykładnicze pod względem liczby bitów (i potrzebuję dużo bitów). Tło: …

34 ds.algorithms graph-theory directed-acyclic-graph

1

Problem Treewidth i NL vs L.

Łączność ST to problem polegający na określeniu, czy istnieje ukierunkowana ścieżka między dwoma wyróżnionymi wierzchołkami i t na ukierunkowanym wykresie G ( V , E ) . To, czy problem ten można rozwiązać w przestrzeni logów, jest od dawna otwartym problemem. Jest to tak zwany N l vs L problemu.ssstttG …

31 cc.complexity-theory graph-theory space-bounded treewidth logspace

5

co jest łatwe dla niewielkich wykluczonych wykresów?

Przybliżenie liczby kolorów wydaje się łatwe na niewielkich wykluczonych wykresach przy użyciu algorytmu Jung / Shah. Jakie są inne przykłady problemów, które są trudne na ogólnych wykresach, ale łatwe na niewielkich wykluczonych wykresach? Aktualizacja 10/24 Wydaje się, że podąża za wynikami Grohe, że wzór, którym jest FPT do testowania na …

31 ds.algorithms graph-theory graph-minor

1

Czy można zdecydować o izomorfizmie grafowym za pomocą niedeterminizmu opartego na pierwiastku kwadratowym?

Ograniczonym nondeterminism łączy funkcję z klasy języków akceptowanych przez deterministycznych maszyny Turinga zasobach ograniczona, w celu utworzenia nowej klasy - . Ta klasa składa się z tych języków, które są akceptowane przez jakąś niedeterministyczną maszynę Turinga przestrzegającą tych samych granic zasobów, jakie są używane do zdefiniowania , ale gdzie może …

30 cc.complexity-theory graph-theory graph-isomorphism nondeterminism

4

Dowody uzyskane jedynie za pomocą teorii grafów spektralnych

Coraz bardziej interesuję się teorią wykresów spektralnych, co wydaje mi się fascynujące, i zacząłem zbierać kilka dokumentów, które muszę jeszcze przeczytać dokładniej niż dotychczas. Jestem jednak ciekawy stwierdzenia, które pojawiło się w kilku źródłach (na przykład tam ), które mówi w istocie, że niektóre wyniki teorii grafów zostały udowodnione przy …

28 graph-theory co.combinatorics proofs spectral-graph-theory

4

Maksymalne klasy, dla których największy niezależny zbiór można znaleźć w czasie wielomianowym?

W ISGCI listy ponad 1100 klas grafów. W przypadku wielu z nich wiemy, czy można ustalić niezależny zestaw w czasie wielomianowym; nazywane są czasem klasami IS-easy . Chciałbym skompilować listę maksymalnych klas IS-easy. Klasy te razem tworzą granicę (znanej) podatności na rozwiązywanie tego problemu. Ponieważ do dowolnej nieskończonej klasy IS-easy …

28 ds.algorithms graph-theory co.combinatorics graph-classes

3

Jak stworzyć losowy wykres, który nie ma cyklu hamiltonowskiego?

Niech klasa A oznacza wszystkie wykresy wielkości które mają cykl hamiltonowski. Z tej klasy łatwo jest utworzyć losowy wykres - weź n izolowanych węzłów, dodaj losowy cykl hamiltonowski, a następnie losowo dodaj krawędzie.nnnnnn Niech klasa B oznacza wszystkie wykresy wielkości które nie mają cyklu hamiltonowskiego. Jak możemy wybrać losowy wykres …

28 ds.algorithms graph-theory

2

Dlaczego topologiczne „sortowanie topologiczne”?

Dlaczego „sortowanie topologiczne” nazywa się „topologicznym”? Czy tylko dlatego, że określa kolejność bez zmiany wierzchołków lub krawędzi - jak pączek i filiżanka kawy są topologicznie równoważne? Dlaczego nie nazywa się to „sortowaniem zależności” lub czymś innym? Dlaczego „topologiczny”? Przyznaję, że jestem zdziwiony.

28 graph-theory graph-algorithms directed-acyclic-graph topology

1

Kolorystyka złożoności wykresów

Załóżmy, że jest wykresem z liczbą barwiącą d = χ ( G ) . Rozważ następującą grę między Alicją i Bobem. W każdej rundzie Alicja wybiera wierzchołek, a Bob odpowiada kolorem { 1 , … , d - 1 } dla tego wierzchołka. Gra kończy się, gdy zostanie odkryta monochromatyczna …

27 reference-request graph-theory co.combinatorics graph-colouring decision-trees

Pytania otagowane jako graph-theory