Pytania otagowane jako graph-theory

Teoria grafów to nauka o grafach, strukturach matematycznych wykorzystywanych do modelowania parowania relacji między obiektami.

1
Właściwości MSO, wykresy płaskie i niewielkie wykresy
Twierdzenie Courcelle'a stwierdza, że ​​każdą właściwość grafu definiowaną w monadycznej logice drugiego rzędu można rozstrzygać w czasie liniowym na wykresach ograniczonej szerokości . Jest to jedno z najbardziej znanych algorytmicznych meta-twierdzeń. Zmotywowany twierdzeniem Courcelle, wysunąłem następujące przypuszczenie: Przypuszczenie : Niech będzie dowolną właściwością definiowaną przez MSO. Jeśli ψ można rozwiązać …
2
Jak generować wykresy ze znaną optymalną osłoną wierzchołków
Szukam sposobu generowania wykresów, aby znana była optymalna osłona wierzchołków. Nie ma ograniczeń co do liczby węzłów lub krawędzi, tylko to, że wykres jest całkowicie połączony. chodzi o wygenerowanie wykresu, który nie jest łatwy do znalezienia optymalnej osłony wierzchołków, aby móc przetestować na niej różne heurystyki Znalazłem artykuł Arthur, J. …
1
Optymalne przetwarzanie wstępne dla niektórych rodzajów zapytań
Załóżmy, że mamy półgrupę z elementami . Naszym celem jest obliczanie produktów .(S,∘)(S,∘)(S,\circ)S={s1,s2,…,sn}S={s1,s2,…,sn}S=\lbrace s_1,s_2,\dots,s_n\rbracesi∘si+1∘⋯∘sjsi∘si+1∘⋯∘sjs_i\circ s_{i+1}\circ \cdots\circ s_j W swoim artykule „Optymalne przetwarzanie wstępne dla odpowiedzi na zapytania produktów on-line” Alon i Schieber udowadniają, że możemy odpowiedzieć na każde takie zapytanie w co najwyżej krokach (gdzie jest odwrotną funkcją Ackermanna), używając …
1
Złożoność unikalnej łączności st
Chciałbym wiedzieć, czy w (niedeterministyczny obszar logów) można rozstrzygnąć następujący problem :N L.NL\mathsf{NL} Biorąc pod uwagę ukierunkowany wykres z dwoma wyróżnionymi wierzchołkami s i t , czy istnieje unikalna ścieżka od s do t w G ?solGGssstttssstttsolGG Czuję, że to może być w ponieważ możemy zdecydować, zarówno jeśli istnieje s …
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
Zwiększanie konkurencyjności solverów SAT dzięki wyspecjalizowanym algorytmom
Jakie są przeszkody w konkurowaniu solverów SAT ze specjalistycznymi algorytmami graficznymi? Innymi słowy, czy jest możliwe oczekiwanie od solverów SAT, które mogą zastąpić rolę projektanta algorytmów - tj. Być w stanie automatycznie rozpoznać strukturę problemu, a następnie rozwiązać go tak szybko, jak specjalistyczny algorytm? Oto kilka przykładów, które moim zdaniem …
3
Rozszerzenie problemu stabilnego małżeństwa?
To może brzmieć bardziej jak pytanie z nauk społecznych niż TCS, ale tak nie jest. Czytając „ Randomizowane algorytmy ” opisujące problem stabilnego małżeństwa, można przeczytać następujące informacje (str. 54) „Można wykazać, że dla każdego wyboru list preferencji istnieje co najmniej jedno stabilne małżeństwo. (Co ciekawe, nie dzieje się tak …
1
Obliczanie maks. Zestawów wolnych od H
Na wykresie niezależny zestaw jest podzbiorem wierzchołków, który nie zawiera krawędzi jako indukowanego podsgrafu. Problem znajdowania największych niezależnych zestawów na wykresie jest fundamentalnym zagadnieniem algorytmicznym i trudnym. Rozważmy bardziej ogólne pytanie dotyczące znalezienia (wielkości) największego zestawu wolnego od H na wykresie, gdzie wolny od H oznacza, że ​​nie indukuje on …
2
Jakiś szybki algorytm problemu z ustawieniem łuku zwrotnego przy minimalnych kosztach?
Na ukierunkowanym wykresie , F ⊂ E , jeśli G ∖ F jest DAG (ukierunkowany wykres acykliczny), F nazywa się zestawem łuku zwrotnego. G=(V,E)G=(V,E)G=(V,E)F⊂EF⊂EF\subset EG∖FG∖FG\setminus FFFF Jeżeli każda krawędź jest powiązana z wagą , problem z zestawem łukowym sprzężenia zwrotnego przy minimalnym koszcie polega na znalezieniu F takiej, że W …
2
Czy sieci społecznościowe są zwykle dobrymi ekspansorami?
Interesują mnie kombinatoryczne właściwości sieci społecznościowych w postaci grafów. Ludzie patrzyli na takie rzeczy, jak rozkład stopni, współczynnik grupowania i ściśliwość tych wykresów. Jedno podstawowe pytanie brzmi: czy te wykresy są zazwyczaj dobrymi wykresami ekspanderów? Czy ktoś sprawdził, powiedzmy, lukę spektralną wykresu na Facebooku? Lub luka widmowa innych dużych sieci …
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.