Pytania otagowane jako graph-theory

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

1
Czy nadal jest możliwe określenie złożoności obliczania szerokości wykresów płaskich?
Dla stałej można określić w czasie liniowym, biorąc pod uwagę wykres wejściowy G , czy jego szerokość wynosi ≤ k . Jednakże, gdy zarówno k jak i G są podane jako dane wejściowe, problem jest trudny NP. ( Źródło ).k∈Nk∈Nk \in \mathbb{N}GGG≤k≤k\leq kkkkGGG Jednak gdy wykres wejściowy jest płaski , …
2
Czy Cheeger jest stały -trwały?
Przeczytałem w niezliczonych artykułach, że wyznaczanie stałej Cheegera na wykresie to -hard. To wydaje się być twierdzeniem ludowym, ale nigdy nie znalazłem ani cytatu, ani dowodu na to stwierdzenie. Komu mam to przypisać? W starym artykule (Isoperimetric Numbers of Graphs, J. Comb. Theory B, 1989) Mohar potwierdza to twierdzenie „dla …
5
Dobre rozmieszczenie miejsc dla sekwencji posiłków i stolików wielkości k dla grupy osób
Biorąc pod uwagę zestaw SS.S osób, chciałbym im usiąść na sekwencji posiłków przy stolikach wielkości . (Oczywiście, jest wystarczająca ilość stolików, aby usiąść przy każdym posiłku.) Chciałbym tak ustawić, aby nikt nie dzielił stołu z tą samą osobą dwa razy. Typowe wartości to ikkk|S||S.||S||S|=45|S.|=45|S|=45k=5k=5k=5 i 6 do 10 posiłków. Mówiąc …
5
Algorytmy aproksymacji dla maksymalnego niezależnego zestawu na specjalnych klasach wykresów
Wiemy, że maksymalny niezależny zestaw (MIS) jest trudny do przybliżenia przy współczynniku dla dowolnego ϵ > 0, chyba że P = NP. Jakie są specjalne klasy wykresów, dla których znane są lepsze algorytmy aproksymacyjne?n1−ϵn1−ϵn^{1-\epsilon}ϵ>0ϵ>0\epsilon > 0 Jakie są wykresy, dla których znane są algorytmy wielomianowe? Wiem, że dla idealnych wykresów …
2
Naturalna redukcja CLIQUE do k-Color
Widoczna jest redukcja z CLIQUE na k-Color, ponieważ oba są NP-Complete. W rzeczywistości mogę go zbudować, tworząc redukcję z CLIQUE do 3-SAT z redukcją z 3-SAT do k-Color. Zastanawiam się, czy istnieje rozsądna bezpośrednia redukcja między tymi problemami. Powiedzmy, redukcję, którą mógłbym wyjaśnić przyjacielowi dość krótko, bez potrzeby opisywania języka …
1
Algorytmy przestrzeni logów na wykresach z ograniczoną szerokością drzewa
Szerokość drzewa mierzy, jak blisko wykresu znajduje się drzewo. Trudno jest obliczyć szerokość drzewa. Najbardziej znany algorytm aproksymacyjny osiąga współczynnik .O ( log n----√)O(logn)O(\sqrt{{\log}n}) Twierdzenie Courcelle'a stwierdza, że dowolną właściwość grafów definiowalną w monadycznej logice drugiego rzędu (MSO2) można rozstrzygać w czasie liniowym na dowolnej klasie wykresów o ograniczonej szerokości …
1
Cliquewidth of Almost Cographs
( Wysłałem to pytanie do MathOverflow dwa tygodnie temu, ale jak dotąd bez ścisłej odpowiedzi) Mam pytanie dotyczące miar szerokości wykresu niekierowanych prostych wykresów. Powszechnie wiadomo, że wykresy (wykresy, które można budować za pomocą operacji rozłącznego łączenia i uzupełniania, poczynając od izolowanych wierzchołków) mają najwyżej 2-krotność (Courcelle i in., Górne …
6
Rodziny wykresów z wielomianowymi algorytmami czasowymi do obliczania liczby chromatycznej
Post zaktualizowany 31 sierpnia : dodałem podsumowanie aktualnych odpowiedzi poniżej oryginalnego pytania. Dzięki za wszystkie interesujące odpowiedzi! Oczywiście każdy może nadal publikować wszelkie nowe ustalenia. Dla których rodzin grafów istnieje algorytm wielomianowy do obliczania liczby chromatycznej ?χ(G)χ(G)\chi(G) Problem można rozwiązać w czasie wielomianowym, gdy (wykresy dwudzielne). Na ogół, gdy χ …
1
Dokładnie płaski przepływ elektryczny
Rozważmy sieć elektryczną zamodelowaną jako płaski wykres G, gdzie każda krawędź reprezentuje rezystor 1 Ω. Jak szybko możemy obliczyć dokładną efektywną rezystancję między dwoma wierzchołkami w G? Równolegle, jak szybko możemy obliczyć dokładny prąd płynący wzdłuż każdej krawędzi, jeśli podłączymy baterię 1 V do dwóch wierzchołków w G? Znane prawa …
2
Wykresy, na których wszystkie najkrótsze ścieżki są unikalne
Szukam nieukierunkowanych, nieważonych połączonych wykresów , w których dla każdej pary u , v ∈ V istnieje unikalna ścieżka u → v, która realizuje odległość d ( u , v ) .G = ( V, E)sol=(V.,mi)G=(V,E)u , v ∈ V.u,v∈V.u,v \in Vu → vu→vu \rightarrow vre( u , v )re(u,v)d(u,v) …
1
Czy istnieje problem, który jest łatwy w przypadku wykresu sześciennego, ale trudny w przypadku wykresów o maksymalnym stopniu 3?
Wykresy sześcienne to wykresy, w których każdy wierzchołek ma stopień 3. Zostały one szeroko zbadane i jestem świadomy, że kilka problemów trudnych dla NP pozostaje trudnych dla NP nawet ograniczonych do podklas grafów sześciennych, ale niektóre inne stają się łatwiejsze. Nadklasą wykresów sześciennych jest klasa grafów o maksymalnym stopniu .Æ …
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.