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

We study the dominating set problem in an online setting. An algorithm isrequired to guarantee competitiveness against an adversary that reveals theinput graph one node at a time. When a node is revealed, the algorithm learnsabout the entire neighborhood of the node (including those nodes that have notyet been revealed). Furthermore, the adversary is required to keep the revealedportion of the graph connected at all times. We present an algorithm thatachieves 2-competitiveness on trees and prove that this competitive ratiocannot be improved by any other algorithm. We also present algorithms thatachieve 2.5-competitiveness on cactus graphs, $(t-1)$-competitiveness on$K_{1,t}$-free graphs, and $\Theta(\sqrt{\Delta})$ for maximum degree $\Delta$graphs. We show that all of those competitive ratios are tight. Then, we studyseveral more general classes of graphs, such as threshold, bipartite planar,and series-parallel graphs, and show that they do not admit competitivealgorithms (that is, when competitive ratio is independent of the input size).Previously, the dominating set problem was considered in a slightly differentinput model, where a vertex is revealed alongside its restricted neighborhood:those neighbors that are among already revealed vertices. Thus, conceptually,our results quantify the value of knowing the entire neighborhood at the time avertex is revealed as compared to the restricted neighborhood. For instance, itwas known in the restricted neighborhood model that 3-competitiveness isoptimal for trees, whereas knowing the neighbors allows us to improve it to2-competitiveness.

Online Domination: The Value of Getting to Know All your Neighbors