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...
Pazur to . Trywialny algorytm wykryje pazur w czasie . Można to zrobić w , gdzie jest wykładnikiem szybkiego mnożenia macierzy, w następujący sposób: weź podrozdział wywołany przez dla każdego wierzchołka i znajdź trójkąt w jego uzupełnienie. O ( n 4 ) O ( n ω + 1 ) ω N [ v ]...
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ą...
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ą...
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...
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 ∈...
Próbuję znaleźć wykres z tymi właściwościami do moich badań, ale niestety nie mogę znaleźć takiego wykresu. Czy ktoś wie, czy istnieje ten wykres lub dlaczego nie jest
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...