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

We consider the following problem called the $k$-Chinese Postman Problem($k$-CPP): given a connected edge-weighted graph $G$ and integers $p$ and $k$,decide whether there are at least $k$ closed walks such that every edge of $G$is contained in at least one of them and the total weight of the edges in thewalks is at most $p$? The problem $k$-CPP is NP-complete, and van Bevern et al.(to appear) and Sorge (2013) asked whether the $k$-CPP is fixed-parametertractable when parameterized by $k$. We prove that the $k$-CPP is indeedfixed-parameter tractable. In fact, we prove a stronger result: the problemadmits a kernel with $O(k^2\log k)$ vertices. We prove that the directedversion of $k$-CPP is NP-complete and ask whether the directed version isfixed-parameter tractable when parameterized by $k$.

Parameterized Complexity of k-Chinese Postman Problem