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

Given a graph $G$ and a digraph $D$ whose vertices are the edges of $G$, weinvestigate the problem of finding a spanning tree of $G$ that satisfies theconstraints imposed by $D$. The restrictions to add an edge in the tree dependon its neighborhood in $D$. Here, we generalize previously investigatedproblems by also considering as input functions $\ell$ and $u$ on $E(G)$ thatgive a lower and an upper bound, respectively, on the number of constraintsthat must be satisfied by each edge. The produced feasibility problem isdenoted by \texttt{G-DCST}, while the optimization problem is denoted by\texttt{G-DCMST}. We show that \texttt{G-DCST} is NP-complete even under strongassumptions on the structures of $G$ and $D$, as well as on functions $\ell$and $u$. On the positive side, we prove two polynomial results, one for\texttt{G-DCST} and another for \texttt{G-DCMST}, and also give a simpleexponential-time algorithm along with a proof that it is asymptotically optimalunder the \ETH. Finally, we prove that other previously studied constrainedspanning tree (\textsc{CST}) problems can be modeled within our framework,namely, the \textsc{Conflict CST}, the \textsc{Forcing CS, the \textsc{At LeastOne/All Dependency CST}, the \textsc{Maximum Degree CST}, the \textsc{MinimumDegree CST}, and the \textsc{Fixed-Leaves Minimum Degree CST}.

A Unifying Model for Locally Constrained Spanning Tree Problems