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 devise a scheme for kernelizing, in sublinear space andpolynomial time, various problems on planar graphs. The scheme exploitsplanarity to ensure that the resulting algorithms run in polynomial time anduse O((sqrt(n) + k) log n) bits of space, where n is the number of vertices inthe input instance and k is the intended solution size. As examples, we applythe scheme to Dominating Set and Vertex Cover. For Dominating Set, we also showthat a well-known kernelization algorithm due to Alber et al. (JACM 2004) canbe carried out in polynomial time and space O(k log n). Along the way, wedevise restricted-memory procedures for computing region decompositions andapproximating the aforementioned problems, which might be of independentinterest.

Kernelizing Problems on Planar Graphs in Sublinear Space and Polynomial Time