PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2001 | Vol. 26, No. 4 | 267-271
Tytuł artykułu

A note on the approximation ratio of graph-coloring

Autorzy
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
The purpose of this note is to prove that the minimum graph coloring can be approximated in polynomial time within approximation ratio less than the maximum between O(n/loge(l n), , and 0(A loglogn/logn) where n and A are the order and the maximum degree of the input-graph. If the maximum is realized by the first quantity, then it outer-performs the best known approximation ratio - function of n - for coloring (M. M. Hallddrsson, A still better performance guarantee for approximate graph coloring), while, if it is realized by the second quantity, it outer-performs the best known approximation ratio, function of A (D. Karger, R. Motwani, and M. Sudan, Approximate graph coloring by semidefinite programming).
Słowa kluczowe
Wydawca

Rocznik
Strony
267-271
Opis fizyczny
Bibliogr. 8 poz.
Twórcy
Bibliografia
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.baztech-article-BPP1-0018-0080
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.