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 Tools annual

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 Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

The Maximum Weight Independent Set Problem (WIS) is a well-known NP-hardproblem. A popular way to study WIS is to detect graph classes for which WIScan be solved in polynomial time, with particular reference to hereditary graphclasses, i.e., defined by a hereditary graph property or equivalently byforbidding one or more induced subgraphs. Given two graphs $G$ and $H$, $G+H$denotes the disjoint union of $G$ and $H$. This manuscript shows that (i) WIScan be solved for ($P_4+P_4$, Triangle)-free graphs in polynomial time, where a$P_4$ is an induced path of four vertices and a Triangle is a cycle of threevertices, and that in particular it turns out that (ii) for every ($P_4+P_4$,Triangle)-free graph $G$ there is a family ${\cal S}$ of subsets of $V(G)$inducing (complete) bipartite subgraphs of $G$, which contains polynomiallymany members and can be computed in polynomial time, such that every maximalindependent set of $G$ is contained in some member of ${\cal S}$. These resultsseem to be harmonic with respect to other polynomial results for WIS on certain[subclasses of] $S_{i,j,k}$-free graphs and to other structure results on[subclasses of] Triangle-free graphs.

Independent sets in ($P_4+P_4$,Triangle)-free graphs