Computing lower bounds for minimum sum coloring and optimum cost chromatic partition

DOI10.1016/J.COR.2019.05.010MaRDI QIDQ2003584zbMATH OpenOpenAlexWikidataFDO

Authors Yanyan Li

Publication date 9 July 2019

Published in Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.cor.2019.05.010

zbMATH Keywords

graph algorithmsgraph coloringlower boundsminimum sum coloringoptimum cost chromatic partition

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Programming involving graphs or networks (90C35)

Recommendations

• Lower bounds for the minimal sum coloring problem
• Minimum sum coloring problem: upper bounds for the chromatic strength
• A new ant colony optimization algorithm for the lower bound of sum coloring problem
• A branch-and-price algorithm for the minimum sum coloring problem
• A heuristic for the minimum cost chromatic partition problem

Cites work

• A memetic algorithm for the minimum sum coloring problem
• A note on the strength and minimum color sum of bipartite graphs
• A tabu search approach for the sum coloring problem
• An effective heuristic algorithm for sum coloring of graphs
• Coloring large graphs based on independent set extraction
• scientific article; zbMATH DE number 1194938 (Why is no real title available?)
• Hybrid evolutionary search for the minimum sum coloring problem of graphs
• Improving the extraction and expansion method for large graph coloring
• Incremental Upper Bound for the Maximum Clique Problem
• Lower bounds for the minimal sum coloring problem
• Minimum sum coloring of \(P_{4}\)-sparse graphs
• On a graph partition problem with application to VLSI layout
• On chromatic sums and distributed resource allocation
• On sum coloring of graphs
• Polynomial algorithm for finding chromatic sum for unicyclic and outerplanar graphs.
• Recent Advances in Constraints

Cited in

(9)

• A branch-and-price algorithm for the minimum sum coloring problem
• Minimum sum coloring problem: upper bounds for the chromatic strength
• A short proof of the NP-completeness of minimum sum interval coloring
• Lower bounds for the minimal sum coloring problem
• Between Colorings and Layouts - Minimum Morphism Cost Problems
• Graph coloring lower bounds from decision diagrams
• On the approximation of Min Split-coloring and Min Cocoloring
• An exact algorithm for the minimum sum coloring problem on partially decomposable graphs
• A fast local search algorithm for minimum sum coloring problem on massive graphs

Describes a project that uses

Uses Software

• EXTRACOL
• DIMACS

This page was built for publication: Computing lower bounds for minimum sum coloring and optimum cost chromatic partition

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