
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

Spanning Distribution Trees of Graphs
Masaki KAWABATA Takao NISHIZEKI
Publication
IEICE TRANSACTIONS on Information and Systems
Vol.E97D
No.3
pp.406412 Publication Date: 2014/03/01
Online ISSN: 17451361
DOI: 10.1587/transinf.E97.D.406
Print ISSN: 09168532 Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer Science —New Trends in Theory of Computation and Algorithm—) Category: Graph Algorithms Keyword: spanning distribution tree, seriesparallel graph, flow, supply, demand, partial ktree,
Full Text: PDF(1.2MB) >>Buy this Article
Summary:
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 NPcomplete even for seriesparallel graphs, and then give a pseudopolynomial time algorithm to solve the problem for a given seriesparallel 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.

