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

In the problem of minimum connected dominating set with routing cost constraint, we are given a graph (G=(V,E)) and a positive integer (alpha ), and the goal is to find the smallest connected dominating set D of G such that, for any two non-adjacent vertices u and v in G, the number of internal nodes on the shortest path between u and v in the subgraph of G induced by (D cup {u,v}) is at most (alpha ) times that in G. For general graphs, the only known previous approximability result is an (O(log n))-approximation algorithm ((n=|V|)) for (alpha = 1) by Ding et al. For any constant (alpha u003e 1), we give an (O(n^{1-frac{1}{alpha }}(log n)^{frac{1}{alpha }}))-approximation algorithm. When (alpha ge 5), we give an (O(sqrt{n}log n))-approximation algorithm. Finally, we prove that, when (alpha =2), unless (NP subseteq DTIME(n^{polylog n})), for any constant (epsilon u003e 0), the problem admits no polynomial-time (2^{log ^{1-epsilon }n})-approximation algorithm, improving upon the (varOmega (log delta )) bound by Du et al., where (delta ) is the maximum degree of G (albeit under a stronger hardness assumption).

On the Approximability and Hardness of the Minimum Connected Dominating Set with Routing Cost Constraint