A 27/26-approximation algorithm for the chromatic sum coloring of bipartitegraphs - Publikacja - MOST Wiedzy

Wyszukiwarka

A 27/26-approximation algorithm for the chromatic sum coloring of bipartitegraphs

Abstrakt

We consider the CHROMATIC SUM PROBLEM on bipartite graphs which appears to be much harder than the classical CHROMATIC NUMBER PROBLEM. We prove that the CHROMATIC SUM PROBLEM is NP-complete on planar bipartite graphs with Delta less than or equal to 5, but polynomial on bipartite graphs with Delta less than or equal to 3, for which we construct an O(n(2))-time algorithm. Hence, we tighten the borderline of intractability for this problem on bipartite graphs with bounded degree, namely: the case Delta = 3 is easy, Delta = 5 is hard. Moreover, we construct a 27/26-approximation algorithm for this problem thus improving the best known approximation ratio of 10/9.

Krzysztof Giaro, Robert Janczewski, Marek Kubale, Michał Małafiejski. (2002). A 27/26-approximation algorithm for the chromatic sum coloring of bipartitegraphs, 2462, 135-145.

Informacje szczegółowe

Kategoria:
Inna publikacyjna praca zbiorowa (w tym materiały konferencyjne)
Typ:
materiały konferencyjne indeksowane w Web of Science
Opublikowano w:
LECTURE NOTES IN COMPUTER SCIENCE nr 2462, strony 135 - 145,
ISSN: 0302-9743
Język:
angielski
Rok wydania:
2002
Opis bibliograficzny:
Giaro K., Janczewski R., Kubale M., Małafiejski M..: A 27/26-approximation algorithm for the chromatic sum coloring of bipartitegraphs, W: , 2002, ,.

wyświetlono 6 razy

Meta Tagi