Pytania otagowane jako random-graphs

2
Które parametry wykresu NIE są skoncentrowane na losowych wykresach?
Dobrze wiadomo, że wiele ważnych parametrów wykresu pokazuje (silne) stężenie na losowych wykresach, przynajmniej w pewnym zakresie prawdopodobieństwa krawędzi. Niektóre typowe przykłady to liczba chromatyczna, maksymalna klika, maksymalna niezależny zestaw maksymalne dopasowanie, numer dominacja, liczba kopii stałe podgrafu, średnicy, maksymalny stopień, numer Choice (lista kolorowania numer), Lovász θθ\theta -liczba, szerokość …
1
Rozdzielanie słów losowymi DFA
Jeden z interesujących otwartych problemów dotyczących DFA wymienionych w Czy są jakieś otwarte problemy dotyczące DFA? jest wielkością DFA wymaganą do oddzielenia dwóch łańcuchów długości nnn . Jestem ciekawy, czy są jakieś wyniki dotyczące zdolności losowego DFA do oddzielania dwóch podanych (nielosowych) ciągów. Wyraźnie losowy DFA o wystarczająco wielu stanach …
2
Jak długo trwa znalezienie krótkiego cyklu na losowym wykresie?
Pozwolić G∼G(n,n−1/2)G∼G(n,n−1/2)G \sim G(n, n^{-1/2}) być losowym wykresem na ≈n3/2≈n3/2\approx n^{3/2}krawędzie Z bardzo dużym prawdopodobieństwemGGG ma wiele 444motocykle. Naszym celem jest wyprodukowanie dowolnego z nich444- motocykle tak szybko, jak to możliwe. Załóżmy, że mamy dostęp do GGG w formie listy sąsiedztwa możemy odnieść sukces ze stałym prawdopodobieństwem w O(n−−√)O(n)O(\sqrt{n}) czas …
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.