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 this paper we give upper bounds on the number of minimal separators and potential maximal cliques of graphs w.r.t. two graph parameters, namely vertex cover (vc) and modular width (mw). We prove that for any graph, the number of minimal separators is \(\mathcal{O}^*(3^{\operatorname{vc}})\) and \(\mathcal{O}^*(1.6181^{\operatorname{mw}})\), the number of potential maximal cliques is \(\mathcal{O}^*(4^{\operatorname{vc}})\) and \(\mathcal{O}^*(1.7347^{\operatorname{mw}})\), and these objects can be listed within the same running times. (The \(\mathcal{O}^*\) notation suppresses polynomial factors in the size of the input.) Combined with known results [3,12], we deduce that a large family of problems, e.g., Treewidth, Minimum Fill-in, Longest Induced Path, Feedback vertex set and many others, can be solved in time \(\mathcal{O}^*(4^{\operatorname{vc}})\) or \(\mathcal{O}^*(1.7347^{\operatorname{mw}})\).

Algorithms Parameterized by Vertex Cover and Modular Width, through Potential Maximal Cliques