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

In the vertex connectivity survivable network design problem we are given anundirected graph G = (V,E) and connectivity requirement r(u,v) for each pair ofvertices u,v. We are also given a cost function on the set of edges. Our goalis to find the minimum cost subset of edges such that for every pair (u,v) ofvertices we have r(u,v) vertex disjoint paths in the graph induced by thechosen edges. Recently, Chuzhoy and Khanna presented a randomized algorithmthat achieves a factor of O(k^3 log n) for this problem where k is the maximumconnectivity requirement. In this paper we derandomize their algorithm to get adeterministic O(k^3 log n) factor algorithm. Another problem of interest is thesingle source version of the problem, where there is a special vertex s and allnon-zero connectivity requirements must involve s. We also give a deterministicO(k^2 log n) algorithm for this problem.

A Deterministic Algorithm for the Vertex Connectivity Survivable Network Design Problem