A network-flow-based lower bound for the minimum weighted integer coloring problem

DOI10.1016/S0020-0190(00)00121-6zbMath0951.68564MaRDI QIDQ1589479

Ju Liu, Jue Xue

Publication date: 12 December 2000

Published in: Information Processing Letters (Search for Journal in Brave)

zbMATH Keywords

algorithmsgraphslower boundsnetwork flowsweighted colorings

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Nonnumerical algorithms (68W05) Deterministic network models in operations research (90B10) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites Work

• Unnamed Item
• Unnamed Item
• Finding maximum cliques in arbitrary and in special graphs
• Solving the minimum weighted integer coloring problem
• Corrigendum: Static frequency assignment in cellular networks
• Minimum Weighted Coloring of Triangulated Graphs, with Application to Maximum Weight Vertex Packing and Clique Finding in Arbitrary Graphs
• A theoretical analysis of backtracking in the graph coloring problem
• Maximizing Submodular Set Functions: Formulations and Analysis of Algorithms
• On colouring random graphs
• Edge‐maximal triangulated subgraphs and heuristics for the maximum clique problem
• A Column Generation Approach for Graph Coloring

This page was built for publication: A network-flow-based lower bound for the minimum weighted integer coloring problem