Pytania otagowane jako graph-colouring

2
Przybliżone zabarwienie wykresu z obiecaną górną granicą na maksymalnym niezależnym zestawie
W mojej pracy powstaje następujący problem: Czy istnieje znany algorytm, który aproksymuje liczbę chromatyczną wykresu bez niezależnego zestawu rzędów 65? (Więc alfa (G) <= 64 jest znane, a | V | / 64 jest trywialną dolną, | V | trywialną górną granicą. Ale czy istnieją lepiej udowodnione przybliżenia w tych …
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ź …
1
Nieprawidłowe płaskie ubarwienie o wielkości elementu monochromatycznego
Rozluźnijmy trochę kolorystykę, tzn. Pozwalamy niewielkiej liczbie sąsiadujących wierzchołków na przypisanie tego samego koloru. Składnik monochromatyczny jest zdefiniowany jako składnik połączony w podsgrafie wywołany przez zestaw wierzchołków, które otrzymują ten sam kolor, a pytanie polega na zapytaniu o minimalną liczbę kolorów potrzebną do pokolorowania wykresu, tak aby największy składnik monochromatyczny …
1
Co wiadomo na temat twardości wskaźnika chromatycznego dla ograniczonych klas grafów?
Jest ładny papier z 1991 roku, który zawiera trzy diagramy dotyczące różnych rodzin klas grafów, pokazujące, co wiadomo na temat twardości wyznaczania dla nich indeksu chromatycznego. Czy są odtąd jakieś wiadomości na ten temat? Najbardziej interesuje mnie to, co wiadomo na temat wykresów z ograniczoną liczbą chromatyczną. Moja ciekawość została …
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.