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

In a graph $G$, a vertex subset $S\subseteq V(G)$ is said to be a dominatingset of $G$ if every vertex not in $S$ is adjacent to a vertex in $S$. Adominating set $S$ of a graph $G$ is called a paired-dominating set if theinduced subgraph $G[S]$ contains a perfect matching. The paired-dominationproblem involves finding a smallest paired-dominating set of $G$. Given anintersection model of an interval graph $G$ with sorted endpoints, Cheng et al.designed an $O(m+n)$-time algorithm for interval graphs and an $O(m(m+n))$-timealgorithm for circular-arc graphs. In this paper, to solve thepaired-domination problem in interval graphs, we propose an $O(n)$-timealgorithm that searches for a minimum paired-dominating set of $G$incrementally in a greedy manner. Then, we extend the results to design analgorithm for circular-arc graphs that also runs in $O(n)$ time.

Linear-Time Algorithms for the Paired-Domination Problem in Interval Graphs and Circular-Arc Graphs