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 Tools annual

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 Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

We consider the selective graph coloring problem, which is a generalizationof the classical graph coloring problem. Given a graph together with apartition of its vertex set into clusters, we want to choose exactly one vertexper cluster so that the number of colors needed to color the selected set ofvertices is minimized. This problem is known to be NP-hard. In this study, wefocus on an exact cutting plane algorithm for selective graph coloring inperfect graphs. Since there exists no suite of perfect graph instances to thebest of our knowledge, we also propose an algorithm to randomly (but notuniformly) generate perfect graphs, and provide a large collection of instancesavailable online. We conduct computational experiments to test our method ongraphs with varying size and densities, and compare our results with astate-of-the-art algorithm from the literature and with solving an integerprogramming formulation of the problem by CPLEX. Our experiments demonstratethat our solution strategy significantly improves the solvability of theproblem.

An Exact Cutting Plane Algorithm to Solve the Selective Graph Coloring Problem in Perfect Graphs