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

Given a simple connected undirected graph G = (V, E), a set X \subseteq V(G),and integers k and p, STEINER SUBGRAPH EXTENSION problem asks if there exists aset S \supseteq X with at most k vertices such that G[S] is p-edge-connected.This is a natural generalization of a well-studied problem STEINER TREE (setp=1 and X as the set of all terminals). In this paper, we initiate the study ofSTEINER SUBGRAPH EXTENSION from the perspective of parameterized complexity andgive a fixed-parameter algorithm parameterized by k and p on graphs of boundeddegeneracy. In case we remove the assumption of the input graph being boundeddegenerate, then the STEINER SUBGRAPH EXTENSION problem becomes W[1]-hard.Besides being an independent advance on the parameterized complexity of networkdesign problems, our result has natural applications. In particular, we use ourresult to obtain singly exponential-time FPT algorithms for several vertexdeletion problem studied in the literature, where the goal is to delete asmallest set of vertices such that (i) the resulting graph belongs to aspecific hereditary graph class, and (ii) the deleted set of vertices induces ap-edge-connected subgraph of the input graph.

Highly Connected Steiner Subgraph -- Parameterized Algorithms and Applications to Hitting Set Problems