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 give the first polynomial-time approximation scheme (PTAS) for the Steinerforest problem on planar graphs and, more generally, on graphs of boundedgenus. As a first step, we show how to build a Steiner forest spanner for suchgraphs. The crux of the process is a clustering procedure calledprize-collecting clustering that breaks down the input instance into separatesubinstances which are easier to handle; moreover, the terminals in differentsubinstances are far from each other. Each subinstance has a relativelyinexpensive Steiner tree connecting all its terminals, and the subinstances canbe solved (almost) separately. Another building block is a PTAS for Steinerforest on graphs of bounded treewidth. Surprisingly, Steiner forest is NP-hardeven on graphs of treewidth 3. Therefore, our PTAS for bounded treewidth graphneeds a nontrivial combination of approximation arguments and dynamicprogramming on the tree decomposition. We further show that Steiner forest canbe solved in polynomial time for series-parallel graphs (graphs of treewidth atmost two) by a novel combination of dynamic programming and minimum cutcomputations, completing our thorough complexity study of Steiner forest in therange of bounded treewidth graphs, planar graphs, and bounded genus graphs.

Approximation Schemes for Steiner Forest on Planar Graphs and Graphs of Bounded Treewidth