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/

Zendy Open

Presents the pdf analysis as premium feature

PDF Analysis

Insights

Presents the summarisation as premium feature

Summarisation

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

We prove a general reduction theorem which allows us to extend bounds for certain graph parameters on cubic graphs to bounds for general graphs taking into account the individual vertex degrees. As applications, we give an algorithm for Max $$2$$2-CSP whose complexity matches the algorithm of Scott and Sorkin in the case of $$d$$d-regular graphs, $$d \\le 5$$d≤5, but is otherwise faster. It also improves on the previously fastest known algorithm in terms of the average degree, given by Golovnev and Kutzkov. Also from the general theorem, we derive a bound for the pathwidth of a general graph which equals that of Fomin et al. and Gaspers for graphs of degree at most $$6$$6, but is smaller otherwise, and use this to give an improved exponential-space algorithm for Max $$2$$2-CSP. Finally we use the general result to give a faster algorithm for Max $$2$$2-CSP on claw-free graphs.

A General Reduction Theorem with Applications to Pathwidth and the Complexity of MAX 2-CSP