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

The idea of enumeration algorithms with polynomial delay is to polynomiallybound the running time between any two subsequent solutions output by theenumeration algorithm. While it is open for more than four decades if allminimal dominating sets of a graph can be enumerated in output-polynomial time,it has recently been proven that pointwise-minimal Roman dominating functionscan be enumerated even with polynomial delay. The idea of the enumerationalgorithm was to use polynomial-time solvable extension problems. We use thisas a motivation to prove that also two variants of Roman dominating functionsstudied in the literature, named perfect and unique response, can be enumeratedwith polynomial delay. This is interesting since Extension Perfect RomanDomination is W[1]-complete if parameterized by the weight of the givenfunction and even W[2]-complete if parameterized by the number verticesassigned 0 in the pre-solution, as we prove. Otherwise, efficient solvabilityof extension problems and enumerability with polynomial delay tend to gohand-in-hand. We achieve our enumeration result by constructing a bijection toRoman dominating functions, where the corresponding extension problem ispolynomimaltime solvable. Furthermore, we show that Unique Response RomanDomination is solvable in polynomial time on split graphs, while Perfect RomanDomination is NP-complete on this graph class, which proves that bothvariations, albeit coming with a very similar definition, do differ in somecomplexity aspects. This way, we also solve an open problem from theliterature.

Perfect Roman Domination and Unique Response Roman Domination