scientific article; zbMATH DE number 1953087

MaRDI QIDQ4414490zbMATH OpenFDO

Authors Marc Demange, Dominique De Werra, Jérôme Monnot, Vangelis Th. Paschos

Publication date 25 July 2003

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/2573/25730114.htm

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Weighted coloring on planar, bipartite and split graphs: Complexity and approximation
• Algorithms and Computation
• Weighted coloring: further complexity and approximability results
• Theoretical Computer Science
• Weighted coloring in trees

Cited in

(23)

• Weighted coloring on planar, bipartite and split graphs: Complexity and approximation
• Weighted coloring: further complexity and approximability results
• Open shop scheduling with synchronization
• A hypocoloring model for batch scheduling
• The maximum saving partition problem
• Maximum-weight stable sets and safe lower bounds for graph coloring
• Parameterized complexity of list coloring and max coloring
• Weighted and locally bounded list-colorings in split graphs, cographs, and partial k-trees
• A note on the Cornaz-Jost transformation to solve the graph coloring problem
• On the probabilistic minimum coloring and minimum k-coloring
• A one-to-one correspondence between colorings and stable sets
• Scheduling on a batch processing machine with split compatibility graphs
• The assignment problem with nearly Monge arrays and incompatible partner indices
• On the Maximum Edge Coloring Problem
• Differential approximation of NP-hard problems with equal size feasible solutions
• Dual parameterization of weighted coloring
• A Semi-exact Algorithm for Quickly Computing A Maximum Weight Clique in Large Sparse Graphs
• Theoretical Computer Science
• Algorithms and Computation
• Max-coloring of vertex-weighted graphs
• On the max-weight edge coloring problem
• Approximation algorithms for the maximum Hamiltonian path problem with specified endpoint(s)
• Dual parameterization of weighted coloring

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4414490)