๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

An algorithm to generate all spanning trees with flow

โœ Scribed by Yi-Kuei Lin

Publisher
Elsevier Science
Year
2002
Tongue
English
Weight
279 KB
Volume
35
Category
Article
ISSN
0895-7177

No coin nor oath required. For personal study only.

โœฆ Synopsis

Spanning tree enumeration in undirected graphs is an important issue and task in many problems encountered in computer network and circuit analysis. This paper discusses the spanning tree with flow for the case that there are flow requirements between each node pair. An algorithm based on minimal paths (MPs) is proposed to generate all spanning trees without flow. The proposed algorithm is a structured approach, which splits the system into structural MPs first, and also all steps in it are easy to follow. (~) 2002 Elsevier Science Ltd. All rights reserved.

๐Ÿ“œ SIMILAR VOLUMES

An algorithm to generate all upper bound
An algorithm to generate all upper boundary points for in terms of minimal cuts
โœ Yi-Kuei Lin ๐Ÿ“‚ Article ๐Ÿ“… 2007 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 242 KB

This paper discusses a stochastic-flow network from single-commodity case to multicommodity case. We propose a performance index, namely the probability that the upper bound of the system capacity is a given vector subject to the budget constraint, to evaluate the quality level for such a network. A

State space partition algorithms for sto
State space partition algorithms for stochastic systems with applications to minimum spanning trees
โœ Alexopoulos, Christos; Jacobson, Jay A. ๐Ÿ“‚ Article ๐Ÿ“… 2000 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 210 KB ๐Ÿ‘ 2 views

We investigated state space partition methods for computing probability measures related to the operation of stochastic systems and present new theoretical results concerning their efficiency. These methods iteratively partition the system state space, producing at each step progressively tighter bo