Weighted coloring on planar, bipartite and split graphs: Complexity and approximation
Authors:
- D. de WerraDWD. de Werra
- M. DemangeMDM. Demange
- B. EscoffierBEB. Escoffier
- J. MonnotJMJ. Monnot
- V.TH. PaschosVPV.TH. Paschos
- 1 February 2009
- journal article
- Published by Elsevier in Discrete Applied Mathematics
- Vol. 157 (4) , 819-832
Abstract
No abstract availableKeywords
This publication has 12 references indexed in Scilit:
- Batch processing with interval graph compatibilities between tasksDiscrete Applied Mathematics, 2008
- Weighted Coloring: further complexity and approximability resultsInformation Processing Letters, 2006
- The maximum saving partition problemOperations Research Letters, 2005
- NP‐completeness of list coloring and precoloring extension on the edges of planar graphsJournal of Graph Theory, 2005
- A coloring problem for weighted graphsInformation Processing Letters, 1997
- Scheduling with incompatible jobsDiscrete Applied Mathematics, 1994
- Minimum Weighted Coloring of Triangulated Graphs, with Application to Maximum Weight Vertex Packing and Clique Finding in Arbitrary GraphsSIAM Journal on Computing, 1991
- Difference graphsDiscrete Applied Mathematics, 1990
- The maximum number of edges in 2K2-free graphs of bounded degreeDiscrete Mathematics, 1990
- Planar Formulae and Their UsesSIAM Journal on Computing, 1982