IEICE TRANSACTIONS on Information
Spanning Distribution Trees of Graphs
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 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.
- Publication
- IEICE TRANSACTIONS on Information Vol.E97-D No.3 pp.406-412
- Publication Date
- 2014/03/01
- Publicized
- Online ISSN
- 1745-1361
- DOI
- 10.1587/transinf.E97.D.406
- Type of Manuscript
- Special Section PAPER (Special Section on Foundations of Computer Science —New Trends in Theory of Computation and Algorithm—)
- Category
- Graph Algorithms
Authors
Masaki KAWABATA
Kwansei Gakuin University
Takao NISHIZEKI
Kwansei Gakuin University
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Masaki KAWABATA, Takao NISHIZEKI, "Spanning Distribution Trees of Graphs" in IEICE TRANSACTIONS on Information,
vol. E97-D, no. 3, pp. 406-412, March 2014, doi: 10.1587/transinf.E97.D.406.
Abstract: 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.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.E97.D.406/_p
Copy
@ARTICLE{e97-d_3_406,
author={Masaki KAWABATA, Takao NISHIZEKI, },
journal={IEICE TRANSACTIONS on Information},
title={Spanning Distribution Trees of Graphs},
year={2014},
volume={E97-D},
number={3},
pages={406-412},
abstract={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.},
keywords={},
doi={10.1587/transinf.E97.D.406},
ISSN={1745-1361},
month={March},}
Copy
TY - JOUR
TI - Spanning Distribution Trees of Graphs
T2 - IEICE TRANSACTIONS on Information
SP - 406
EP - 412
AU - Masaki KAWABATA
AU - Takao NISHIZEKI
PY - 2014
DO - 10.1587/transinf.E97.D.406
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E97-D
IS - 3
JA - IEICE TRANSACTIONS on Information
Y1 - March 2014
AB - 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.
ER -
English
