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 Open

Presents the pdf analysis as premium feature

PDF Analysis

Insights

Presents the summarisation as premium feature

Summarisation

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

We consider two graph optimization problems called vector domination andtotal vector domination. In vector domination one seeks a small subset S ofvertices of a graph such that any vertex outside S has a prescribed number ofneighbors in S. In total vector domination, the requirement is extended to allvertices of the graph. We prove that these problems (and several variantsthereof) cannot be approximated to within a factor of clnn, where c is asuitable constant and n is the number of the vertices, unless P = NP. We alsoshow that two natural greedy strategies have approximation factors ln D+O(1),where D is the maximum degree of the input graph. We also provide exactpolynomial time algorithms for several classes of graphs. Our results extend,improve, and unify several results previously known in the literature.

On the approximability and exact algorithms for vector domination and related problems in graphs