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

We consider a variant of the path cover problem, namely, the$k$-fixed-endpoint path cover problem, or kPC for short, on interval graphs.Given a graph $G$ and a subset $\mathcal{T}$ of $k$ vertices of $V(G)$, a$k$-fixed-endpoint path cover of $G$ with respect to $\mathcal{T}$ is a set ofvertex-disjoint paths $\mathcal{P}$ that covers the vertices of $G$ such thatthe $k$ vertices of $\mathcal{T}$ are all endpoints of the paths in$\mathcal{P}$. The kPC problem is to find a $k$-fixed-endpoint path cover of$G$ of minimum cardinality; note that, if $\mathcal{T}$ is empty the statedproblem coincides with the classical path cover problem. In this paper, westudy the 1-fixed-endpoint path cover problem on interval graphs, or 1PC forshort, generalizing the 1HP problem which has been proved to be NP-completeeven for small classes of graphs. Motivated by a work of Damaschke, where heleft both 1HP and 2HP problems open for the class of interval graphs, we showthat the 1PC problem can be solved in polynomial time on the class of intervalgraphs. The proposed algorithm is simple, runs in $O(n^2)$ time, requireslinear space, and also enables us to solve the 1HP problem on interval graphswithin the same time and space complexity.

The 1-fixed-endpoint Path Cover Problem is Polynomial on Interval Graph