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

Search

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

Abstract

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.

Cite as

Full text

full text is not available in portal

Keywords

Details

Category:
Conference activity
Type:
materiały konferencyjne indeksowane w Web of Science
Published in:
LECTURE NOTES IN COMPUTER SCIENCE no. 2462, pages 135 - 145,
ISSN: 0302-9743
Language:
English
Publication year:
2002
Bibliographic description:
Giaro K., Janczewski R., Kubale M., Małafiejski M..: A 27/26-approximation algorithm for the chromatic sum coloring of bipartitegraphs, W: , 2002, ,.
Verified by:
Gdańsk University of Technology

seen 130 times

Recommended for you

Meta Tags