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/

Zendy Plus

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

Zendy Tools

Zendy Open

We consider node-weighted survivable network design (SNDP) in planar graphsand minor-closed families of graphs. The input consists of a node-weightedundirected graph $G=(V,E)$ and integer connectivity requirements $r(uv)$ foreach unordered pair of nodes $uv$. The goal is to find a minimum weightedsubgraph $H$ of $G$ such that $H$ contains $r(uv)$ disjoint paths between $u$and $v$ for each node pair $uv$. Three versions of the problem areedge-connectivity SNDP (EC-SNDP), element-connectivity SNDP (Elem-SNDP) andvertex-connectivity SNDP (VC-SNDP) depending on whether the paths are requiredto be edge, element or vertex disjoint respectively. Our main result is an$O(k)$-approximation algorithm for EC-SNDP and Elem-SNDP when the input graphis planar or more generally if it belongs to a proper minor-closed family ofgraphs; here $k=\max_{uv} r(uv)$ is the maximum connectivity requirement. Thisimproves upon the $O(k \log n)$-approximation known for node-weighted EC-SNDPand Elem-SNDP in general graphs [Nutov, TALG'12]. We also obtain an $O(1)$approximation for node-weighted VC-SNDP when the connectivity requirements arein $\{0,1,2\}$; for higher connectivity our result for Elem-SNDP can be used ina black-box fashion to obtain a logarithmic factor improvement over currentlyknown general graph results. Our results are inspired by, and generalize, thework of [Demaine, Hajiaghayi and Klein, TALG'14] who obtained constant factorapproximations for node-weighted Steiner tree and Steiner forest problems inplanar graphs and proper minor-closed families of graphs via a primal-dualalgorithm.

Node-Weighted Network Design in Planar and Minor-Closed Families of Graphs