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 the classicMaximum Weight Independent Set problem, we are given a graphG with a nonnegative weight function on its vertices, and the goal is to find an independent set inG of maximum possible weight. While the problem is NP-hard in general, we give a polynomial-time algorithm working on anyP 6 -free graph, that is, a graph that has no path on 6 vertices as an induced subgraph. This improves the polynomial-time algorithm onP 5 -free graphs of Lokshtanov et al. [15 ] and the quasipolynomial-time algorithm onP 6 -free graphs of Lokshtanov et al. [14 ]. The main technical contribution leading to our main result is enumeration of a polynomial-size family ℱ of vertex subsets with the following property: For every maximal independent setI in the graph, ℱ contains all maximal cliques of some minimal chordal completion ofG that does not add any edge incident to a vertex ofI .

Polynomial-time Algorithm for Maximum Weight Independent Set on P 6 -free Graphs

Polynomial-time Algorithm for Maximum Weight Independent Set on P ₆ -free Graphs