A Basic Study on the Existence of the Pairs of Edge-Disjoint Steiner Tree Connecting Multiple Terminals on Graphs

DOI Web Site 3 References

Bibliographic Information

Other Title
  • グラフ上の複数拠点を多重に連結する辺素なシュタイナー木対の存在に関する基礎的考察
  • From the perspective of road network multiplicity evaluation
  • 道路網の多重性評価の観点から

Description

<p>This study makes clear the existence conditions of the pairs of edge-disjoint Steiner tree that are effective in analyzing the multiplicity of road networks. First, we derived that the number of terminals t and the number of cycles ℓ has the relationship ℓ≧t−1, in the pair of edge-disjoint Steiner trees. Therefore, we proved that a pair of edge-disjoint Steiner trees can be constructed by connecting two terminals in a cycle and connecting all terminals in a chain of these cycles. Finally, we found that if there exists a pair of edge-disjoint Steiner trees in the graph G, there is the relation of e−v≧t−2(e: edge, v: vertex), and we confirmed this in some examples.</p>

Journal

References(3)*help

See more

Keywords

Details 詳細情報について

Report a problem

Back to top