On local search for the generalized graph coloring problem

DOI10.1016/S0167-6377(02)00165-7zbMath1013.90071MaRDI QIDQ1870000

Jan Karel Lenstra, Tjark Vredeveld

Publication date: 4 May 2003

Published in: Operations Research Letters (Search for Journal in Brave)

zbMATH Keywords

local searchgraph coloringworst-case analysis

Mathematics Subject Classification ID

Search theory (90B40) Coloring of graphs and hypergraphs (05C15)

Related Items (5)

Local 7-coloring for planar subgraphs of unit disk graphs ⋮ Complexity of local search for the \(p\)-median problem ⋮ A mathematical model and a metaheuristic approach for a memory allocation problem ⋮ A NEW APPROACH TO THE VERTEX COLORING PROBLEM ⋮ Complexity and Approximability of Optimal Resource Allocation and Nash Equilibrium over Networks

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• How easy is local search?
• Simple Local Search Problems that are Hard to Solve
• An Efficient Heuristic Procedure for Partitioning Graphs
• P-Complete Approximation Problems
• Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications
• Scheduling to Minimize Interaction Cost

This page was built for publication: On local search for the generalized graph coloring problem