Solving the minimum-weighted coloring problem

DOI10.1002/NET.1028MaRDI QIDQ2748384zbMATH OpenOpenAlexFDO

Authors Massimiliano Caramia, Paolo Dell'Olmo

Publication date 14 October 2001

Published in Networks (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/net.1028

zbMATH Keywords

weighted coloring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• New lower bounds on the weighted chromatic number of a graph
• Minimum Weighted Coloring of Triangulated Graphs, with Application to Maximum Weight Vertex Packing and Clique Finding in Arbitrary Graphs
• Solving the minimum weighted integer coloring problem
• scientific article; zbMATH DE number 4144006
• Weighted coloring: further complexity and approximability results

Cites work

• A Column Generation Approach for Graph Coloring
• A lower bound on the chromatic number of Mycielski graphs
• A Pruning Procedure for Exact Graph Coloring
• A Sufficient Condition for Backtrack-Free Search
• CHECKCOL: improved local search for graph coloring
• Consistency in networks of relations
• Finding maximum cliques in arbitrary and in special graphs
• scientific article; zbMATH DE number 437527 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 956855 (Why is no real title available?)
• Network-based heuristics for constraint-satisfaction problems
• New methods to color the vertices of a graph
• Weighted and unweighted maximum clique algorithms with upper bounds from fractional coloring

Cited in

(11)

• An algorithm for constructing a weight-controlled subset and its application to graph coloring problem
• Solving the minimum weighted integer coloring problem
• Partially concurrent open shop scheduling with integral preemptions
• Weighted and unweighted maximum clique algorithms with upper bounds from fractional coloring
• Four decades of research on the open-shop scheduling problem to minimize the makespan
• Bounded colouring motivated by the limited resource partially concurrent open shop problem
• On the minimum load coloring problem
• Exact weighted vertex coloring via branch-and-price
• New lower bounds on the weighted chromatic number of a graph
• scientific article; zbMATH DE number 2230238 (Why is no real title available?)
• On new algorithmic techniques for the weighted vertex coloring problem

Describes a project that uses

Uses Software

• GraphBase

This page was built for publication: Solving the minimum-weighted coloring problem

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