New lower bounds on the weighted chromatic number of a graph
Massimiliano Caramia; Jirí Fiala
Discussiones Mathematicae Graph Theory (2004)
- Volume: 24, Issue: 2, page 183-195
- ISSN: 2083-5892
Access Full Article
top
Abstract
topHow to cite
topMassimiliano Caramia, and Jirí Fiala. "New lower bounds on the weighted chromatic number of a graph." Discussiones Mathematicae Graph Theory 24.2 (2004): 183-195. <http://eudml.org/doc/270419>.
@article{MassimilianoCaramia2004,
abstract = {In this paper we present theoretical and algorithmic results for the computation of lower bounds on the chromatic number of a weighted graph. In particular, we study different ways of a possible improvement of the lower bound offered by a maximum weighted clique. Based on our findings we devise new algorithms and show their performance on random graphs.},
author = {Massimiliano Caramia, Jirí Fiala},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {combinatorial analysis; computational analysis; optimization; coloring; algorithms; weighted clique; NP-completeness},
language = {eng},
number = {2},
pages = {183-195},
title = {New lower bounds on the weighted chromatic number of a graph},
url = {http://eudml.org/doc/270419},
volume = {24},
year = {2004},
}
TY - JOUR
AU - Massimiliano Caramia
AU - Jirí Fiala
TI - New lower bounds on the weighted chromatic number of a graph
JO - Discussiones Mathematicae Graph Theory
PY - 2004
VL - 24
IS - 2
SP - 183
EP - 195
AB - In this paper we present theoretical and algorithmic results for the computation of lower bounds on the chromatic number of a weighted graph. In particular, we study different ways of a possible improvement of the lower bound offered by a maximum weighted clique. Based on our findings we devise new algorithms and show their performance on random graphs.
LA - eng
KW - combinatorial analysis; computational analysis; optimization; coloring; algorithms; weighted clique; NP-completeness
UR - http://eudml.org/doc/270419
ER -
References
top- [1] D. Brelaz, New methods to color the vertices of a graph, Communications of the ACM 22 (1979) 251-256, doi: 10.1145/359094.359101. Zbl0394.05022
- [2] M. Caramia and P. Dell'Olmo, Iterative coloring extension of a maximum clique, Naval Research Logistics 48 (2001) 518-550, doi: 10.1002/nav.1033.
- [3] M. Caramia and P. Dell'Olmo, Solving the minimum weighted coloring problem, Networks 38 (2001) 88-101, doi: 10.1002/net.1028.
- [4] B. Descartes, Solution to advanced problem, No 4526. Amer. Math. Monthly 61 (1954) 532.
- [5] M.R. Garey and D.S. Johnson, Computers and Intractability (Freeman and Co.: San Francisco, 1979). Zbl0411.68039
- [6] M. Kubale, Introduction to Computational Complexity and Algorithmic Graph Coloring (Wydawnictwo GTN, Gdańsk, 1998).
- [7] M. Kubale and B. Jackowski, A generalized implicit enumeration algorithm for graph coloring, Communications of the ACM 28 (1985) 412-418, doi: 10.1145/3341.3350.
- [8] A. Mehrotra and M.A. Trick, A column generation approach for graph coloring, INFORMS J. on Computing 8 (1996) 344-354, doi: 10.1287/ijoc.8.4.344. Zbl0884.90144
- [9] T.J. Sager and S. Lin, A Pruning procedure for exact graph coloring, ORSA J. on Computing 3 (1993) 226-230, doi: 10.1287/ijoc.3.3.226. Zbl0768.68177
- [10] E.C. Sewell, An Improved Algorithm for Exact Graph Coloring, in: D.S. Johnson and M.A. Trick, eds., DIMACS Series in Computer Mathematics and Theoretical Computer Science 26 (1996) 359-373. Zbl0866.05025
NotesEmbed ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.