Let <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$D=(V(D), A(D))$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>D</mi> <mo>=</mo> <mo stretchy="false">(</mo> <mi>V</mi> <mo stretchy="false">(</mo> <mi>D</mi> <mo stretchy="false">)</mo> <mo>,</mo> <mi>A</mi> <mo stretchy="false">(</mo> <mi>D</mi> <mo stretchy="false">)</mo> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> be a digraph, and let <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$S\subseteq V(D)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>S</mi> <mo>⊆</mo> <mi>V</mi> <mo stretchy="false">(</mo> <mi>D</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> with <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$r\in S$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>r</mi> <mo>∈</mo> <mi>S</mi> </mrow> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$|S|\ge 2$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">|</mo> <mi>S</mi> <mo stretchy="false">|</mo> <mo>≥</mo> <mn>2</mn> </mrow> </math></EquationSource> </InlineEquation>, a directed (S, r)-Steiner path (or an (S, r)-path) is a directed path P started at r such that <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$S\subseteq V(P)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>S</mi> <mo>⊆</mo> <mi>V</mi> <mo stretchy="false">(</mo> <mi>P</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>. Two (S, r)-paths are arc-disjoint if they have no common arcs. Two arc-disjoint (S, r)-paths are internally disjoint if the set of common vertices of them is S. The Arc-disjoint (resp. Internally-disjoint) Directed Steiner Path Packing is as follows: Let D be a digraph and let <InlineEquation ID="IEq6"> <EquationSource Format="TEX">$r\in S\subseteq V(D)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>r</mi> <mo>∈</mo> <mi>S</mi> <mo>⊆</mo> <mi>V</mi> <mo stretchy="false">(</mo> <mi>D</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>, we try to find the largest number of arc-disjoint (resp. internally disjoint) (S, r)-paths. This type of problems and related topics attract much attention from researchers as it has very strong backgrounds of applications in the areas of VLSI circuit design and computer networks. In this paper, we study the complexity and algorithms of directed Steiner path packing problems and investigate the structure to obtain sharp bounds and precise values of the directed path connectivity which is highly related to directed Steiner path packing problems and is a natural generalization of classical connectivity of undirected graphs and digraphs.

Algorithmic and structural results of directed Steiner path packing and directed path connectivity

期刊论文
发表日期：

2025年12月4日

查看全文

Yuefang Sun,
Xiaoyan Zhang

摘要

Let $D=(V(D), A(D))$ $D = (V (D), A (D))$ be a digraph, and let $S\subseteq V(D)$ $S \subseteq V (D)$ with $r\in S$ $r \in S$ and $|S|\ge 2$ $| S | \geq 2$ , a directed (S, r)-Steiner path (or an (S, r)-path) is a directed path P started at r such that $S\subseteq V(P)$ $S \subseteq V (P)$ . Two (S, r)-paths are arc-disjoint if they have no common arcs. Two arc-disjoint (S, r)-paths are internally disjoint if the set of common vertices of them is S. The Arc-disjoint (resp. Internally-disjoint) Directed Steiner Path Packing is as follows: Let D be a digraph and let $r\in S\subseteq V(D)$ $r \in S \subseteq V (D)$ , we try to find the largest number of arc-disjoint (resp. internally disjoint) (S, r)-paths. This type of problems and related topics attract much attention from researchers as it has very strong backgrounds of applications in the areas of VLSI circuit design and computer networks. In this paper, we study the complexity and algorithms of directed Steiner path packing problems and investigate the structure to obtain sharp bounds and precise values of the directed path connectivity which is highly related to directed Steiner path packing problems and is a natural generalization of classical connectivity of undirected graphs and digraphs.