Pytania otagowane jako hypergraphs

2
Rozpoznawanie wykresów liniowych hipergraphów
Wykres liniowy hipergrafu jest (prostym) wykresem G mającym krawędzie H, ponieważ wierzchołki o dwóch krawędziach H sąsiadują w G, jeśli mają niepuste przecięcie. Hypergraph to r- hipergraph, jeśli każda jego krawędź ma co najwyżej r wierzchołków.HHHGGGHHHHHHGGGrrrrrr Jaka jest złożoność następującego problemu: Czy na podstawie wykresu istnieje 3- hipergraph H, taki …
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ź …
4
Jakie właściwości grafów płaskich uogólniają się na wyższe wymiary / hipergrrafy?
Płaska wykres przedstawia wykres, który może być osadzony w płaszczyźnie, bez konieczności przekraczania krawędzie. Niech będzie - jednolitym hipergraphem, tj. Hipergraphem takim, że wszystkie jego hipergezy mają rozmiar k.kG = ( X, E)G=(X,E)G=(X,E)kkk Wykonano już pewne prace związane z osadzaniem hiperrafatów w płaszczyźnie (w kontekście klastrowania lub innej aplikacji), ale …
4
Jakie są główne trudności w przechodzeniu od wykresów do hipergraphów?
W kombinatoryce i informatyce istnieje wiele przykładów, w których możemy analizować problem teoretyczny na wykresach, ale w przypadku analogu hipergrraficznego problemu brakuje naszych narzędzi. Jak myślisz, dlaczego problemy często stają się znacznie trudniejsze w przypadku 3-jednolitych hiperrafów niż w przypadku 2-jednolitych wykresów? Jakie są podstawowe trudności? Jedną kwestią jest to, …
1
CSP z nieograniczoną ułamkową szerokością hipertree
za´za´\acute{\rm a}H ∈ P T I M EH.H.HH.H.H∈ P.T.jaM.mi∈P.T.jaM.mi\in PTIME Definicje itp. Świetny przegląd standardowych rozkładów drzew i ich szerokości znajduje się tutaj (Dziękujemy z góry, JeffE!). Niech H.H.H będzie hipergrafatem. Następnie dla hipergraph H.H.H i mapowania γ: E( H) → [ 0 , ∞ )γ:mi(H.)→[0,∞)\gamma : E(H) \rightarrow [0,\infty) …
2
Konsekwencje dolnych granic dla -net na przybliżeniu
Wielu tutaj prawdopodobnie zdaje sobie sprawę z ostatnich superliniowych dolnych granic Alon dla -net w naturalnych ustawieniach geometrycznych [PDF] . Chciałbym wiedzieć, co, jeśli w ogóle, taka dolna granica implikuje przybliżenie powiązanych problemów z zestawem Cover / Hitting Set. ϵϵ\epsilon Aby być nieco bardziej szczegółowym, rozważ rodzinę przestrzeni zasięgu, na …
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.