Wyniki wyszukiwania - BazTech

Ograniczanie wyników

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: F-decomposition graphs

Sortuj według:

Ogranicz wyniki do:

O złożoności problemów F-dekompozycji grafów>

Jesse-Józefczyk K.

Zeszyty Naukowe Wydziału ETI Politechniki Gdańskiej. Technologie Informacyjne

2007

T. 13

419-426

W pracy tej zostało przedstawionych kilka problemów związanych z F-dekompozycją grafów i jej złożonością obliczeniową. F-dekompozycję będziemy utożsamiać z częściowym dwukolorowaniem wierzchołków grafu. Kolorowanie to musi spełniać kilka warunków, z których najważniejszym jest to, aby krawędzie czerwono-niebieskie tworzyły zbiór rozspajający dany graf oraz wraz z wierzchołkami w tych kolorach nie indukowały pewnych grafów dwudzielnych.

This paper presents selected problems concerning F-decomposition of graphs and its complexity. We identify the F-decomposition with a colouring of vertices of a graph. This colouring must satisfy several conditions and the most important of them is that the red-blue edges must be a cut-set of the given graph and together with the vertices coloured red and blue they cannot induce some bipartite graphs.