Directed Steiner path packing and directed path connectivity

arXiv2211.04025MaRDI QIDQ6416487FDOQ6416487

Authors: Yuefang Sun 

Publication date: 8 November 2022

Abstract: For a digraph $D=(V(D),A(D))$, and a set $SsubseteqV(D)$ with $rinS$ and $|S|geq2$, a directed $(S,r)$-Steiner path or, simply, an $(S,r)$-path is a directed path $P$ started at $r$ with $SsubseteqV(P)$. Two $(S,r)$-paths are said to be arc-disjoint if they have no common arc. Two arc-disjoint $(S,r)$-paths are said to be internally disjoint if the set of common vertices of them is exactly $S$. Let $kapp{a}_{S,r}^p(D)$ (resp. $lambd{a}_{S,r}^p(D)$) be the maximum number of internally disjoint (resp. arc-disjoint) $(S,r)$-paths in $D$. The directed path $k$-connectivity of $D$ is defined as ${\displaystyle }$kappa^p_k(D)= min {kappa^p_{S,r}(D)mid Ssubseteq V(D), |S|=k, rin S}.${\displaystyle }$ Similarly, the directed path $k$-arc-connectivity of $D$ is defined as ${\displaystyle }$lambda^p_k(D)= min {lambda^p_{S,r}(D)mid Ssubseteq V(D), |S|=k, rin S}.${\displaystyle }$ The directed path $k$-connectivity and directed path $k$-arc-connectivity are also called directed path connectivity which extends the path connectivity on undirected graphs to directed graphs and could be seen as a generalization of classical connectivity of digraphs. In this paper, we obtain complexity results for $kapp{a}_{S,r}^p(D)$ on Eulerian digraphs and symmetric digraphs, and $lambd{a}_{S,r}^p(D)$ on general digraphs. We also give bounds for the parameters $kapp{a}_k^p(D)$ and $lambd{a}_k^p(D)$.

This page was built for publication: Directed Steiner path packing and directed path connectivity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6416487)