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 eternal vertex cover problem is a dynamic variant of the classical vertexcover problem. It is NP-hard to compute the eternal vertex cover number ofgraphs and known algorithmic results for the problem are very few. This paperpresents a linear time recursive algorithm for computing the eternal vertexcover number of cactus graphs. Unlike other graph classes for which polynomialtime algorithms for eternal vertex cover number are based on efficientcomputability of a known lower bound directly derived from minimum vertexcover, we show that it is a certain substructure property that helps theefficient computation of eternal vertex cover number of cactus graphs. Anextension of the result to graphs in which each block is an edge, a cycle or abiconnected chordal graph is also presented.

A Linear Time Algorithm for Computing the Eternal Vertex Cover Number of Cactus Graphs