PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2004 | 24 | 2 | 183-195
Tytuł artykułu

New lower bounds on the weighted chromatic number of a graph

Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
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.
Wydawca
Rocznik
Tom
24
Numer
2
Strony
183-195
Opis fizyczny
Daty
wydano
2004
Twórcy
  • IAC - Istituto per le Applicazioni del Calcolo "M. Picone", CNR - Viale del Policlinico, 137 - 00161 Roma, Italy
autor
  • Institute of Theoretical Computer Science (ITI), Charles University, Faculty of Mathematics and Physics, Malostranské nám. 2/25, 118 00, Prague, Czech Republic
Bibliografia
  • [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.
  • [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).
  • [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.
  • [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.
  • [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.
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1224
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ć.