Wyniki wyszukiwania - BazTech

Ograniczanie wyników

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: oszacowanie górne

Sortuj według:

Ogranicz wyniki do:

Nowe oszacowania górne dla liczby chromatycznej grafu i ich zastosowania algorytmiczne

Borowiecki P.

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

2007

T. 13

434-442

Liczba chromatyczna grafu jest najmniejszą liczbą kolorów niezbędnych do pokolorowania jego wierzchołków w taki sposób, aby żadne dwa sąsiednie wierzchołki nie miały tego samego koloru. W ogólnym przypadku problem wyznaczenia liczby chromatycznej grafu jest problemem NP-trudnym. W pracy tej wprowadzamy pojęcie funkcji potencjału określonej na wierzchołkach grafu i stosujemy ją w celu uzyskania nowych górnych oszacowań liczby chromatycznej. Porównujemy uzyskane oszacowania z ich klasycznymi odpowiednikami zależnymi od stopni wierzchołków. Wartości funkcji potencjału wykorzystujemy również do zdefiniowania nowych uporządkowań zbioru wierzchołków, co prowadzi do zdefiniowania dwóch nowych sekwencyjnych algorytmów kolorowania.

Chromatic number of a graph is defined as the smallest number of colors required to color its vertices such that there does not exist a pair of adjacent vertices of the same color. In general it is NP-hard to determine the chromatic number of a graph. Within this paper we introduce the notion of a potential function of a graph defined on its vertex set and use it to establish new upper bounds on the chromatic number. The bounds are compared with their classical counterparts that use vertex degrees instead of potentials. Moreover, the values of a potential function are used to define new vertex orderings, what leads to new sequential graph coloring algorithms.