Pytania otagowane jako partial-order

Porządek częściowy to relacja binarna na zbiorze, który jest zwrotny, antysymetryczny i przechodni.

5
Pozytywne uporządkowanie topologiczne
Załóżmy, że mam ukierunkowany wykres acykliczny z wagami liczb rzeczywistych na jego wierzchołkach. Chcę znaleźć uporządkowanie topologiczne DAG, w którym dla każdego prefiksu uporządkowania topologicznego suma wag jest nieujemna. Lub jeśli wolisz terminologię teoretyczną, mam ważoną częściową kolejność i chcę liniowego rozszerzenia, aby każdy prefiks miał nieujemną wagę. Co wiadomo …
1
Jak szybko możemy obliczyć zbiór poetów w zestawie rodziny zestawów?
Biorąc pod uwagę określoną rodzinę podzbiorów uniwersum . Niech a my chcemy odpowiedzieć to .FF\mathcal{F}UUUS1,S2∈FS1,S2∈FS_1,S_2 \in \mathcal FS1⊆S2S1⊆S2S_1 \subseteq S_2 Szukam struktury danych, która pozwoli mi szybko odpowiedzieć na to pytanie. Moja aplikacja pochodzi z teorii grafów, w której chcę sprawdzić, czy usunięcie wierzchołka i jego sąsiedztwa pozostawia izolowane wierzchołki, …
4
Najgorsza liczba pytań potrzebna do nauczenia się monotonicznego orzeczenia nad zestawem
Rozważmy skończoną posetę ponad elementów, a nieznany monotoniczny predykat nad (tj. Dla dowolnego , , jeśli i to ) . Mogę ocenić , podając jeden węzeł i sprawdzając, czy utrzymuje, czy nie. Moim celem jest określenie dokładnie zestawu węzłów tak, że P (x) utrzymuje, przy użyciu jak najmniejszej liczby ocen …
1
Czy liczenie maksymalnych klików na wykresie nieporównywalności # P jest kompletne?
To pytanie jest motywowane pytaniem MathOverflow Peng Zhanga . Valiant wykazał, że zliczanie maksymalnych klików na wykresie ogólnym jest zakończone metodą # P, ale co jeśli ograniczymy się do wykresów nieporównywalności (tzn. Chcemy policzyć maksymalne antichains w skończonym zestawie)? To pytanie wydaje się na tyle naturalne, że podejrzewam, że zostało …
1
Minimalne elementy monotonicznego predykatu nad zestawem mocy
Rozważ monotoniczny predykat PPP nad zestawem mocy 2|n|2|n|2^{|n|}(uporządkowane przez włączenie). Przez „monotoniczny” rozumiem: ∀x,y∈2|n|∀x,y∈2|n|\forall x, y \in 2^{|n|}tak, że x ⊂ yx⊂yx \subset y , jeśli P.( x )P(x)P(x) to P.( y)P(y)P(y) . Szukam algorytmu, aby znaleźć wszystkie minimalne elementy P.PP , tj. x ∈ 2| n |x∈2|n|x \in 2^{|n|}takie, …
1
Pozytywne uporządkowanie topologiczne, weź 2
Jest to kontynuacja ostatniego pytania Davida Eppsteina i jest motywowana tymi samymi problemami. Załóżmy, że mam wierzchołek z ciężarami na liczbach rzeczywistych na jego wierzchołkach. Początkowo wszystkie wierzchołki są nieoznaczone. Mogę zmienić zestaw zaznaczonych wierzchołków, albo (1) zaznaczając wierzchołek bez nieoznaczonych poprzedników, albo (2) odznaczając wierzchołek bez zaznaczonych następców. (Zatem …
2
Określanie, co można osiągnąć przez permutację elementów grupy nieprzemiennej
Ustalić skończoną grupę . Interesuje mnie następujący problem decyzyjny: dane wejściowe to niektóre elementy G z częściowym porządkiem na nich, a pytanie brzmi, czy istnieje permutacja elementów, która spełnia porządek i jest taka, że ​​skład elementów w tym porządek daje neutralny element grupy e .GGGGGGeee Formalnie problem testu GGG jest …
2
Problemy z kratą
Dużo pracy poświęcono problemom obliczeniowym dla zamówień częściowych (np. Rozpoznawanie, numer skoku, rozpoznawanie wykresu porównywalności itp.). Jestem ciekawy, jaką pracę wykonano dla sieci. Szukałem wokoło i nie znalazłem podobnej pracy dla krat. W szczególności jestem zainteresowany tym, czy zbadano następujące problemy z siecią: Rozpoznawanie krat: czy przy danym DAG czy …
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.