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

The VertexCover problem is proven to be computationally hard in differentways: It is NP-complete to find an optimal solution and even NP-hard to find anapproximation with reasonable factors. In contrast, recent experiments suggestthat on many real-world networks the run time to solve VertexCover is waysmaller than even the best known FPT-approaches can explain. Similarly, greedyalgorithms deliver very good approximations to the optimal solution inpractice.  We link these observations to two properties that are observed in manyreal-world networks, namely a heterogeneous degree distribution and highclustering. To formalize these properties and explain the observed behavior, weanalyze how a branch-and-reduce algorithm performs on hyperbolic random graphs,which have become increasingly popular for modeling real-world networks. Infact, we are able to show that the VertexCover problem on hyperbolic randomgraphs can be solved in polynomial time, with high probability.  The proof relies on interesting structural properties of hyperbolic randomgraphs. Since these predictions of the model are interesting in their ownright, we conducted experiments on real-world networks showing that theseproperties are also observed in practice. When utilizing the same structuralproperties in an adaptive greedy algorithm, further experiments suggest that,on real instances, this leads to better approximations than the standard greedyapproach within reasonable time.

Solving Vertex Cover in Polynomial Time on Hyperbolic Random Graphs