English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

The vertex coloring problem asks for the minimum number of colors that can beassigned to the vertices of a given graph such that each two adjacent verticesget different colors. For this NP-hard problem, a variety of integer linearprogramming (ILP) models have been suggested. Among them, the assignment basedand the partial-ordering based ILP models are attractive due to theirsimplicity and easy extendability. Moreover, on sparse graphs, both modelsturned out to be among the strongest exact approaches for solving the vertexcoloring problem. In this work, we suggest additional strengthening constraintsfor the partial-ordering based ILP model, and show that they lead to improvedlower bounds of the corresponding LP relaxation. Our computational experimentsconfirm that the new constraints are also leading to practical improvements. Inparticular, we are able to find the optimal solution of a previously openinstance from the DIMACS benchmark set for vertex coloring problems

Strengthened Partial-Ordering Based ILP Models for the Vertex Coloring Problem