Pytania otagowane jako graph-classes

4
Maksymalne klasy, dla których największy niezależny zbiór można znaleźć w czasie wielomianowym?
W ISGCI listy ponad 1100 klas grafów. W przypadku wielu z nich wiemy, czy można ustalić niezależny zestaw w czasie wielomianowym; nazywane są czasem klasami IS-easy . Chciałbym skompilować listę maksymalnych klas IS-easy. Klasy te razem tworzą granicę (znanej) podatności na rozwiązywanie tego problemu. Ponieważ do dowolnej nieskończonej klasy IS-easy …
1
Odniesienia do wykresów wolnych od (nieparzystych, dziurawych)?
Wykresy wolne od X to te, które nie zawierają wykresu z X jako indukowanego podgrupy. Otwór jest cykl co najmniej 4 wierzchołków. Odd-dziura jest dziura z nieparzystej liczby wierzchołków. Antihole jest dopełnieniem otworem. Wykresy wolne od (nieparzystej dziury, nieparzystej antihole) są dokładnie idealnymi grafami; to jest twierdzenie Strong Perfect Graph …
3
Klasy wykresów z łatwym cyklem hamiltonowskim, ale z TSP NP-twardym
Hamiltona Cykl Problem (HC) polega na znalezieniu cykl, który przechodzi przez wszystkie wierzchołki w danym undirected wykresu. Problem komiwojażera (TSP), polega na znalezieniu się cykl, który przechodzi przez wszystkie wierzchołki w danej krawędzi wykresu ważonych minimalizuje całkowitą odległość, mierzoną przez sumę mas krawędzi w cyklu. HC jest szczególnym przypadkiem TSP …
1
Czy ta klasa wykresów ma nazwę?
Jest sformułowany przez rozszerzenie wykresów progowych . Biorąc pod uwagę wykres progowy gdzie jest kliką, a jest niezależnym zbiorem, moje rozszerzenie jest następujące: Każdy wierzchołek można zastąpić nową kliką tak, że wierzchołki mają to samo sąsiedzi .( C, Ja)(do,ja)(C,I)dodoCjajaIv ∈ Iv∈jav\in IK.vK.vK_vK.vK.vK_vvvv Wydaje mi się, że należało to zbadać, ale …
1
Czy wykresy „rodzaju zewnętrznego” mają stałą szerokość grzbietu?
Niech i przez zestaw wszystkich wykresów, które mogą być osadzone na powierzchni rodzaju tak, aby wszystkie wierzchołki znajdowały się na zewnętrznej powierzchni . Na przykład jest zbiorem zewnętrznych wykresów płaskich. Czy szerokość wykresów w być ograniczona przez jakąś funkcję ?G k k G 0 G k kk∈Nk∈Nk\in\mathbb{N}GkGkG_kkkkG0G0G_0GkGkG_kkkk Drugi kierunek oczywiście …
2
Nazwij klasę wykresów: Rozłączne połączenie kliki i zbioru niezależnego
Pozwolić solsolG być wykresem będącym rozłącznym związkiem kliki i niezależnym zbiorem, tj. G =K.n1+K.n2)¯¯¯¯¯¯¯¯=K.n1+jan2).sol=K.n1+K.n2)¯=K.n1+jan2).G = K_{n_1} + \overline{K_{n_2}} = K_{n_1} + I_{n_2} . Klasa grafów wszystkich takich wykresów charakteryzuje się zabronionym indukowanym zestawem a zatem jest to przecięcie wykresu skupień i wykresu podziału (lub progu).H ={2K.2),P.3)}H.={2)K.2),P.3)}\mathcal{H} = \{2K_2, P_3\} 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.