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

Let F be a fixed finite obstruction set of graphs and G be a graph revealedin an online fashion, node by node. The online Delayed F-Node-Deletion Problem(F-Edge-Deletion Problem}) is to keep G free of every H in F by deleting nodes(edges) until no induced subgraph isomorphic to any graph in F can be found inG. The task is to keep the number of deletions minimal.  Advice complexity is a model in which an online algorithm has access to abinary tape of infinite length, on which an oracle can encode information toincrease the performance of the algorithm. We are interested in the minimumnumber of advice bits that are necessary and sufficient to solve a deletionproblem optimally.  In this work, we first give essentially tight bounds on the advice complexityof the Delayed F-Node-Deletion Problem and F-Edge-Deletion Problem where Fconsists of a single, arbitrary graph H. We then show that the gadget used toprove these results can be utilized to give tight bounds in the case of nodedeletions if F consists of either only disconnected graphs or only connectedgraphs. Finally, we show that the number of advice bits that is necessary andsufficient to solve the general Delayed F-Node-Deletion Problem is heavilydependent on the obstruction set F. To this end, we provide sets for which thisnumber is either constant, logarithmic or linear in the optimal number ofdeletions.

Advice Complexity bounds for Online Delayed F-Node-, H-Node- and H-Edge-Deletion Problems