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

Vertex Descent is a local search algorithm which forms the basis of a widespectrum of tabu search, simulated annealing and hybrid evolutionary algorithmsfor graph colouring. These algorithms are usually treated as experimental andprovide strong results on established benchmarks. As a step towards studyingthese heuristics analytically, an analysis of the behaviour of Vertex Descentis provided. It is shown that Vertex Descent is able to find feasiblecolourings for several types of instances in expected polynomial time. Thisincludes 2-colouring of paths and 3-colouring of graphs with maximum degree 3.The same also holds for 3-colouring of a subset of 3-colourable graphs withmaximum degree 4. As a consequence, Vertex Descent finds a 3-colouring inexpected polynomial time for the smallest graph for which Br\'elaz's heuristicDSATUR needs 4 colours. On the other hand, Vertex Descent may fail for forestswith maximum degree 3 with high probability.

An Analysis of a Simple Local Search Algorithm for Graph Colouring