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 Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

We provide CONGEST model algorithms for approximating minimum weighted vertexcover and the maximum weighted matching. For bipartite graphs, we show that a$(1+\varepsilon)$-approximate weighted vertex cover can be computeddeterministically in polylogarithmic time. This generalizes a correspondingresult for the unweighted vertex cover problem shown in [Faour, Kuhn; OPODIS'20]. Moreover, we show that in general weighted graph families that are closedunder taking subgraphs and in which we can compute an independent set of weightat least a $\lambda$-fraction of the total weight, one can compute a$(2-2\lambda +\varepsilon)$-approximate weighted vertex cover inpolylogarithmic time in the CONGEST model. Our result in particular impliesthat in graphs of arboricity $a$, one can compute a$(2-1/a+\varepsilon)$-approximate weighted vertex cover.  For maximum weighted matchings, we show that a $(1-\varepsilon)$-approximatesolution can be computed deterministically in polylogarithmic CONGEST rounds(for constant $\varepsilon$). We also provide a more efficient randomizedalgorithm. Our algorithm generalizes results of [Lotker, Patt-Shamir, Pettie;SPAA '08] and [Bar-Yehuda, Hillel, Ghaffari, Schwartzman; PODC '17] for theunweighted case.  Finally, we show that even in the LOCAL model and in bipartite graphs ofdegree $\leq 3$, if $\varepsilon<\varepsilon_0$ for some constant$\varepsilon_0>0$, then computing a $(1+\varepsilon)$-approximation for theunweighted minimum vertex cover problem requires $\Omega\big(\frac{\logn}{\varepsilon}\big)$ rounds. This generalizes aresult of [G\"o\"os, Suomela;DISC '12], who showed that computing a $(1+\varepsilon_0)$-approximation insuch graphs requires $\Omega(\log n)$ rounds.

Distributed CONGEST Approximation of Weighted Vertex Covers and Matchings