Arc-disjoint in-trees in directed graphs
スポンサーリンク
概要
- 論文の詳細を見る
Given a directed graph D = (V,A) with a set of d specified vertices S = {s 1,…, s d } ⊆ V and a function f: S → ℕ where ℕ denotes the set of natural numbers, we present a necessary and sufficient condition such that there exist Σ i=1 d f(s i ) arc-disjoint in-trees denoted by T i,1,T i,2,…, $$ T_{i,f(s_0 )} $$ for every i = 1,…,d such that T i,1,…,$$ T_{i,f(s_0 )} $$ are rooted at s i and each T i,j spans the vertices from which s i is reachable. This generalizes the result of Edmonds [2], i.e., the necessary and sufficient condition that for a directed graph D=(V,A) with a specified vertex s∈V, there are k arc-disjoint in-trees rooted at s each of which spans V. Furthermore, we extend another characterization of packing in-trees of Edmonds [1] to the one in our case.
論文 | ランダム
- Low driving voltage amorphous In-Ga-Zn-O thin film transistors with small subthreshold swing using high-κ Hf-Si-O dielectrics
- 半導体製造プロセスにおけるウェハ上良品取得可能領域解析方式
- タンニンと共存物質との相互作用の効果(第8報)天然色素の変色防止効果
- 82 新種大環状加水分解性タンニンオリゴマーの構造 : 36員環構造のタンニンおよび関連化合物(ポスター発表の部)
- 血清中の殺菌因子Ra-reactive factorの測定法の検討