Narzędzia help

Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
first previous next last
cannonical link button

http://yadda.icm.edu.pl:80/baztech/element/bwmeta1.element.baztech-article-BPG5-0031-0053

Czasopismo

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

Tytuł artykułu

Algorytmiczne oszacowania liczby chromatycznej grafu

Autorzy Borowiecki, P. 
Treść / Zawartość
Warianty tytułu
EN Algorithmic bounds on the chromatic number of a graph
Języki publikacji PL
Abstrakty
PL 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.
EN 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.
Słowa kluczowe
PL liczba chromatyczna grafu   funkcja potencjału grafu   liczba Welsha-Powella   liczba Szekersa-Wilfa   algorytmy sekwencyjne   algorytmy porządkujące wierzchołki  
EN chromatic number of graph   NP-hard   graph potential function   Welsh-Powell numbers   Szekeres-Wilf numbers   sequential algorithms   algorithm ordering vertices  
Wydawca Wydział Elektroniki, Telekomunikacji i Informatyki Politechniki Gdańskiej
Czasopismo Zeszyty Naukowe Wydziału ETI Politechniki Gdańskiej. Technologie Informacyjne
Rocznik 2008
Tom T. 15
Strony 159--164
Opis fizyczny Bibliogr. 7 poz., tab.
Twórcy
autor Borowiecki, P.
  • Wydział Matematyki, Informatyki i Ekonometrii, Uniwersytet Zielonogórski
Bibliografia
[1] Acharya B. D., Vartak M. N.: On the construction oj graphs with given constant valence-difference(s) on each of their lines, Wiss. Zeitschrifte TH Ilmenau, 23 (6) (1977) 33-60.
[2] Borowiecki P.: Nowe oszacowania górne dla liczby chromatycznej grafu i ich zastosowania algorytmiczne, Zesz. Nauk. Wydziału ETI Politechniki Gdańskiej, Ser. Technologie Informacyjne, 13 (2007) 435-442.
[3] Kosowski A., Manuszewski K.: Classical coloring of graphs. W: Graph Colorings, Kubale M. (red.), Contemporary Mathematics 352, American Mathematical Society, Providence, 2004,1-19
[4] Matula D.W.: A min-max theorem for graphs with application to graph coloring, SIAM Rev. 10 (1968) 481-482.
[5] Matula D.W., Marble G., Isaacson J. D.: Graph coloring algorithms. W: Graph Theory and Computing, Read R. C. (red.), Academic Press, London, 1972, 109-122.
[6] Szekeres G., Wilf S. H.: An inequality for the chromatic number of a graph, Joumal of Combinatorial Theory, 4 (1968) 1-3.
[7] Welsh D. J. A., Powell M. B.: An upper bound for the chromatic number of a graph and its application to timetabling problem, Comp. J. 10 (1967) 85-86.
Kolekcja BazTech
Identyfikator YADDA bwmeta1.element.baztech-article-BPG5-0031-0053
Identyfikatory