Pytania otagowane jako co.combinatorics

Pytania dotyczące kombinatoryki i dyskretnych struktur matematycznych

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 …
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 …
4
Złożoność zastosowania permutacji w miejscu
Ku mojemu zaskoczeniu nie udało mi się znaleźć artykułów na ten temat - prawdopodobnie przeszukałem niewłaściwe słowa kluczowe. Mamy więc tablicę czegokolwiek i funkcję na jej indeksach; jest permutacją.ffffff Jak zmienić kolejność tablic zgodnie z pamięcią i czasem działania tak blisko i jak to możliwe?fffO(1)O(1)O(1)O(n)O(n)O(n) Czy są jakieś dodatkowe warunki, …
1
Dobre kody dekodowalne przez obwody liniowe?
Szukam kodów korygujących błędy następującego typu: kody binarne o stałej szybkości, dekodowalny z pewnej stałej części błędów za pomocą dekodera możliwego do zaimplementowania jako logiczny obwód o rozmiarze , gdzie N jest długością kodowania.O ( N)O(N)O(N)N.NN Trochę tła: Spielman, w liniowych kodowalnych i dekodowalnych kodach korygujących błędy , dał kody …
1
Czy istnieje zwykły język drzewa, w którym średnia wysokość drzewa o rozmiarze nie jest ani ani ?
Definiujemy zwykły język drzewa, tak jak w książce TATA : Jest to zestaw drzew akceptowany przez niedeterministyczny automat skończonego drzewa (rozdział 1) lub, równoważnie, zbiór drzew wygenerowany przez zwykłą gramatykę drzewa (rozdział 2). Oba formalizmy są bardzo podobne do znanych analogów strunowych. Czy istnieje zwykły język drzewa, w którym średnia …
4
Liczenie słów przyjętych przez zwykłą gramatykę
W przypadku zwykłego języka (NFA, DFA, gramatyki lub wyrażenia regularnego), jak można policzyć liczbę słów akceptowanych w danym języku? Interesujące są zarówno „z dokładnie n literami”, jak i „z najwyżej n literami”. Margareta Ackerman ma dwa artykuły na powiązany temat wyliczania słów zaakceptowanych przez NFA, ale nie byłem w stanie …
2
Maksymalne / maksymalne niezależne zestawy
Czy jest coś znanego o klasie grafów z właściwością, że wszystkie maksymalne niezależne zbiory mają tę samą liczność, a zatem są maksymalnymi IS? Na przykład weź zestaw punktów na płaszczyźnie i rozważ wykres przecięcia między wszystkimi segmentami między parami punktów w zestawie. (segmenty-> wierzchołki, przecięcia-> krawędzie). Ten wykres będzie miał …
1
Lemma regularności dla rzadkich wykresów
Lemma regularności Szemerediego mówi, że każdy gęsty wykres może być aproksymowany jako połączenie O ( 1 )O(1)O(1) wielu dwustronnych grafów ekspanderów. Dokładniej, istnieje podział większości wierzchołków na zestawy O ( 1 )O(1)O(1) tak że większość par zestawów tworzy dwustronne ekspandery (liczba zestawów w partycji i parametr rozszerzenia zależą od parametru …
2
Dokładna liczba porównań do obliczenia mediany
Tom III sztuki programowania komputerowego Knutha (rozdział 5, werset 3.2) zawiera poniższą tabelę zawierającą dokładną minimalną liczbę porównań wymaganych do wybrania tego najmniejszego elementu z nieposortowanego zestawu wielkości , dla wszystkich . Ta tabela, wraz z dobrze znanymi wyrażeniami typu zamkniętego i , reprezentuje większość stanu techniki w 1976 r. …
2
Złożoność ustalenia, czy ustalony wykres jest niewielki w stosunku do innego
W rezultacie przez Robertson Seymour wykazuje algorytm do testowania, czy stałej wykres jest minor . Mam dwa i pół pytania na ten temat:O ( n3))O(n3))O(n^3)solsolGH.H.H 1) Wygląda na to, że od tego czasu wprowadzono ulepszenia tego algorytmu. Jaki jest obecnie najbardziej znany algorytm? 2a) Co ludzie przypuszczają, że są optymalnym …
2
Złożoność obliczeniowa liczników indukowanych liczeniem, które dopuszczają idealne dopasowanie
Biorąc pod uwagę nieukierunkowany i nieważony wykres a jeszcze całkowita k , co jest złożoność obliczeniowa zestawów zliczania wierzchołków S ⊆ V tak, że | S | = k, a podgrupa G ograniczona do zbioru wierzchołków S dopuszcza idealne dopasowanie? Czy złożoność # P jest kompletna? Czy istnieje odniesienie do …
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.