Wyniki wyszukiwania - BazTech

Ograniczanie wyników

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: chromatic number of graph

Sortuj według:

Ogranicz wyniki do:

Algorytmiczne oszacowania liczby chromatycznej grafu

Borowiecki P.

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

2008

T. 15

159-164

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 jest problemem NP-trudnym, stąd duże zainteresowanie parametrami graf owym i, które można wykorzystać do opisu oszacowań wartości liczby chromatycznej. W pracy tej omawiamy własności parametrów wywodzących się z pojęcia funkcji potencjału grafu oraz badamy ich powiązania z klasycznymi parametrami takimi jak liczba Welsha-Powella oraz liczba Szekeresa-Wilfa. Przedstawiamy także wyniki eksperymentalnego porównania dwóch znanych algorytmów sekwencyjnych z algorytmami porządkującymi wierzchołki według wartości funkcji potencjału.

The chromatic number of a graph is the smallest number of colors required to color its vertices such that no two adjacent vertices share a color. In the general case determining the chromatic number of a graph is NP-hard, thus any graph invariants useful in bounding it are of great interest. Within this paper we discuss the properties of the invariants originating in the notion of a potential function. We study their interdependencies and the relationships to the classical Welsh-Powell and Szekeres- Wilf numbers. We also present the results of experimental comparison of two known sequential algorithms to the algorithms that use orderings of vertices with respect to their potentials.