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

In this paper, we perform theoretical analyses on the behaviour of anevolutionary algorithm and a randomised search algorithm for the dynamic vertexcover problem based on its dual formulation. The dynamic vertex cover problemhas already been theoretically investigated to some extent and it has beenshown that using its dual formulation to represent possible solutions can leadto a better approximation behaviour. We improve some of the existing results,i.e. we find a linear expected re-optimization time for a (1+1) EA tore-discover a 2-approximation when edges are dynamically deleted from thegraph. Furthermore, we investigate a different setting for applying thedynamism to the problem, in which a dynamic change happens at each step with aprobability $P_D$. We also expand these analyses to the weighted vertex coverproblem, in which weights are assigned to vertices and the goal is to find acover set with minimum total weight. Similar to the classical case, the dynamicchanges that we consider on the weighted vertex cover problem are adding andremoving edges to and from the graph. We aim at finding a maximal solution forthe dual problem, which gives a 2-approximate solution for the vertex coverproblem. This is equivalent to the maximal matching problem for the classicalvertex cover problem.

Runtime Analysis of RLS and (1+1) EA for the Dynamic Weighted Vertex Cover Problem