Advancing Branch-and-Price for Graph Coloring: New Pricing Strategies and Benchmark Results
This paper proposes BPCOL+, an exact branch-and-price algorithm for the Graph Coloring Problem. The algorithm integrates enhanced pricing strategies based on Zero-Suppressed Binary Decision Diagrams (ZDDs) for solving the pricing problem associated with the maximal-stable-set-based set-covering formulation. After computing upper and lower bounds at the root node using heuristic procedures and column generation, BPCOL+ reduces the size of the ZDD by applying maximal stable set reduction techniques that exploit alternative dual vectors. Computational experiments on the 137 DIMACS benchmark…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2606.08356
curl -X POST /api/v1/records/arxiv/2606.08356/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2606.08356/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'