Pytania otagowane jako co.combinatorics

Pytania dotyczące kombinatoryki i dyskretnych struktur matematycznych

5
Aplikacje kombinatoryki addytywnej w projektowaniu algorytmów
Czytam ankiety Trevisana i Lovetta dotyczące zastosowań dodatku kombinatorycznego w TCS. Większość tych aplikacji ma złożoność obliczeniową , np. Niższe granice. Zastanawiam się, czy kombinatoryka addytywna znalazła również zastosowania w projektowaniu algorytmów . Motywacja mojego pytania jest następująca: chociaż związek między kombinatoryką addytywną a złożonością wydaje się dość naturalny, jestem …
1
Wydajny algorytm dla istnienia permutacji z sekwencją różnic?
To pytanie jest motywowane tym postem. Czy potrafisz określić sumę dwóch permutacji w czasie wielomianowym? oraz moje zainteresowanie obliczeniowymi właściwościami permutacji. Sekwencja różnic permutacji π liczb 1 , 2 , … n + 1 jest tworzona przez znalezienie różnicy między każdą dwiema sąsiednimi liczbami w permutacji π . Innymi słowy, …
1
Czy istnieje książka / artykuł przeglądowy przedstawiający hierarchie klas językowych, właściwości zamknięcia itp
Obecnie prowadzę badania nad językiem formalnym, które obejmują klasy języków powyżej zwykłego, ale poniżej kontekstowego. Patrzę na takie rzeczy, jak maszyny zliczające z odwróceniem, maszyny liczące na jednym stosie, deterministyczne CFL itp. Zastanawiam się, czy ktokolwiek wie o dobrej książce lub opracowaniu, które opisuje właściwości tych języków. Większość tego, na …
2
Mały wykres z odstępem między liczbą chromatyczną a liczbą chromatyczną wektorową?
Szukam małego wykresu GGG którego wektorowa liczba chromatyczna jest mniejsza niż liczba chromatyczna, χv(G)&lt;χ(G)χv(G)&lt;χ(G)\chi_v(G)<\chi(G) . ( GGG zawiera wektor chromatycznej liczba qqq , jeśli istnieje zadanie x:V→Rdx:V→Rdx\colon V \rightarrow \mathbf R^d , gdzie intuicyjnie wektory związane z sąsiednimi wierzchołkami są oddalone od siebie Warunkiem jest, ⟨x(v),x(w)⟩≤−1/(q−1)⟨x(v),x(w)⟩≤−1/(q−1)\langle x(v), x(w)\rangle \leq -1/(q-1) …
2
Programowanie liczb całkowitych ze stałą liczbą zmiennych
Słynny artykuł H. Lenstry Integer Programowanie z ustaloną liczbą zmiennych z 1983 r. Stwierdza, że ​​programy liczb całkowitych o ustalonej liczbie zmiennych można rozwiązać wielomianem czasowym długości danych. Interpretuję to w następujący sposób. Programowanie liczb całkowitych ogólnie jest nadal NP-kompletne, ale jeśli mój typowy rozmiar problemu (powiedzmy około 10.000 zmiennych, …
1
Kombinatoryczne osadzanie wykresu
Tutaj: http://www.planarity.org/Klein_elementary_graph_theory.pdf (w osadzeniach rozdziałów) podano definicję kombinatorycznego osadzania wykresu płaskiego. (z definicją ścian i tak dalej) Choć można go łatwo zastosować do dowolnego wykresu, definiują wykres płaski jako wykres, dla którego obowiązuje formuła Eulera (zakładając, że wykres jest połączony). Zrozumiałe jest, że dla każdego wykresu płaskiego definicja ścian w …
1
Implementacja Wilfa-Zeilbergera i powiązanych metod
Książka A = B autorstwa Petkovseka, Wilfa i Zeilbergera opisuje algorytmy do obliczania różnych sum dwumianów. AFAIK, algorytmy te są wciąż ulepszane przez różnych autorów. Czy wiesz, gdzie możemy znaleźć najbardziej aktualne implementacje tych algorytmów? A czy wiesz, czy istnieją implementacje w niektórych darmowych programach, takich jak Sage ?
1
Cytowanie pokazujące osoby niepełnoletnie są nieletnimi topologicznymi dla wykresów podrzędnych
Jeśli jest wykresem w stopniu maksymalnie 3 i jest minor H , a G jest topologiczna minor H .solGGH.HHsolGGH.HH Wikipedia cytuje ten wynik z „Teorii grafów” Diestela. Jest wymieniony jako Prop 1.7.4 w najnowszej wersji książki. W książce brakuje dowodu lub cytowania. Czy miejsce pobytu znane jest z (oryginalnego) dowodu …
1
Czy wykresy „rodzaju zewnętrznego” mają stałą szerokość grzbietu?
Niech i przez zestaw wszystkich wykresów, które mogą być osadzone na powierzchni rodzaju tak, aby wszystkie wierzchołki znajdowały się na zewnętrznej powierzchni . Na przykład jest zbiorem zewnętrznych wykresów płaskich. Czy szerokość wykresów w być ograniczona przez jakąś funkcję ?G k k G 0 G k kk∈Nk∈Nk\in\mathbb{N}GkGkG_kkkkG0G0G_0GkGkG_kkkk Drugi kierunek oczywiście …
1
Wydajny algorytm do niemal optymalnego kolorowania krawędzi hipergraphów
Problemy z kolorowaniem wykresów są już wystarczająco trudne dla większości ludzi . Mimo to będę musiał być trudny i zapytać o barwienie metodą hypergraph. Pytanie. Jakie są skuteczne algorytmy do znalezienia w przybliżeniu optymalnego zabarwienia krawędzi dla hipergraphów jednolitych k? Detale --- Hypergraph k-uniform to taki, w którym każda krawędź …
2
Czy teoria pierwszego rzędu struktury skończonej ograniczyła rangę kwantyfikatora?
Niech będzie dowolną skończoną strukturą. Czy jego teoria pierwszego rzędu ograniczyła rangę kwantyfikatora w tym sensie, że istnieje taki, że dla wszystkich z jest z i ?AA\mathfrak{A} T:=TH(A)T:=TH(A) \mathfrak{T} := \mathfrak{TH}(\mathfrak{A}) q∈Nq∈N q\in\mathbb{N} φ∈Tφ∈T \varphi\in\mathfrak{T} qr(φ)&gt;qqr(φ)&gt;q qr(\varphi) > q φ′∈Tφ′∈T \varphi'\in\mathfrak{T} qr(φ′)≤qqr(φ′)≤q qr(\varphi')\leq q φ′≡φφ′≡φ \varphi'\equiv\varphi
1
Oblicz najniższy wymiarowy polytop z danego zestawu wektorów znakowych
Biorąc pod uwagę zestaw hiperpłaszczyzn określonych przez wektory normalne , wszystkie typy komórek (lub wektory znakowe) to wszystkie wektory t ∈ { + , - } m, dla których istnieje wektor tak, że i dla wszystkich . W tym przypadku oznacza wewnętrzny produkt, a oznacza znak ( lubh1,…,hm∈Rdh1,…,hm∈Rdh_1,\dots,h_m \in \mathbf …
4
Problemy wielomianowe w klasach grafów zdefiniowanych przez zabronione indukowane cykliczne podgrupy
Skrzyżowane z MO . Niech CCC będzie klasą grafu zdefiniowaną przez skończoną liczbę zabronionych indukowanych podrożników, z których wszystkie są cykliczne (zawierają co najmniej jeden cykl). Czy istnieją problemy związane z grafem trudnym dla NP, które można rozwiązać w czasie wielomianowym dla CCC innego niż Clique i Clique? Jeśli dobrze …
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.