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 Plus

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

Zendy Tools

Zendy Open

Many NP-hard problems, such as Dominating Set, are FPT parameterized byclique-width. For graphs of clique-width $k$ given with a $k$-expression,Dominating Set can be solved in $4^k n^{O(1)}$ time. However, no FPT algorithmis known for computing an optimal $k$-expression. For a graph of clique-width$k$, if we rely on known algorithms to compute a $(2^{3k}-1)$-expression viarank-width and then solving Dominating Set using the $(2^{3k}-1)$-expression,the above algorithm will only give a runtime of $4^{2^{3k}} n^{O(1)}$. Therehave been results which overcome this exponential jump; the best knownalgorithm can solve Dominating Set in time $2^{O(k^2)} n^{O(1)}$ by avoidingconstructing a $k$-expression [Bui-Xuan, Telle, and Vatshelle. Fast dynamicprogramming for locally checkable vertex subset and vertex partitioningproblems. Theoret. Comput. Sci., 2013. doi:10.1016/j.tcs.2013.01.009]. Weimprove this to $2^{O(k\log k)}n^{O(1)}$. Indeed, we show that for a graph ofclique-width $k$, a large class of domination and partitioning problems(LC-VSP), including Dominating Set, can be solved in $2^{O(k\log{k})}n^{O(1)}$. Our main tool is a variant of rank-width using the rank of a $0$-$1$matrix over the rational field instead of the binary field.

Faster Algorithms For Vertex Partitioning Problems Parameterized by Clique-width