Spanning Distribution Trees of Graphs

• KAWABATA Masaki

  School of Science and Technology, Kwansei Gakuin University

• NISHIZEKI Takao

  School of Science and Technology, Kwansei Gakuin University

抄録

Let G be a graph with a single source w, assigned a positive integer called the supply. Every vertex other than w is a sink, assigned a nonnegative integer called the demand. Every edge is assigned a positive integer called the capacity. Then a spanning tree T of G is called a spanning distribution tree if the capacity constraint holds when, for every sink v, an amount of flow, equal to the demand of v, is sent from w to v along the path in T between them. The spanning distribution tree problem asks whether a given graph has a spanning distribution tree or not. In the paper, we first observe that the problem is NP-complete even for series-parallel graphs, and then give a pseudo-polynomial time algorithm to solve the problem for a given series-parallel graph G. The computation time is bounded by a polynomial in n and D, where n is the number of vertices in G and D is the sum of all demands in G.

収録刊行物

• IEICE Transactions on Information and Systems

  IEICE Transactions on Information and Systems E97.D (3), 406-412, 2014

  一般社団法人 電子情報通信学会

キーワード

• spanning distribution tree
• series-parallel graph
• flow
• supply
• demand
• partial <i>k</i>-tree

詳細情報

• CRID: 1390001204377660416
• NII論文ID: 130003394855
• DOI: 10.1587/transinf.e97.d.406
• ISSN: 17451361
• ISSN: 09168532
• Web Site: https://www.jstage.jst.go.jp/article/transinf/E97.D/3/E97.D_406/_pdf
• 本文言語コード: en
• データソース種別:
  • JaLC
  • Crossref
  • CiNii Articles
  • KAKEN
• 抄録ライセンスフラグ: 使用不可