𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Multiple cover problem on undirected flow networks

✍ Scribed by Hiroshi Tamura; Hidehito Sugawara; Masakazu Sengoku; Shoji Shinoda

Publisher
John Wiley and Sons
Year
2000
Tongue
English
Weight
187 KB
Volume
84
Category
Article
ISSN
1042-0967

No coin nor oath required. For personal study only.

✦ Synopsis

Problems concerning the optimum location of various devices installed in transport, communication, and other types of networks relate to the so-called location on network problems. In this paper, we show how an expanded multiple cover problem can be solved in polynomial time for the case of an undirected flow network, which is a special case of the location problem on flow networks. Up to now, such problems were solved in polynomial time for conditions when values of the flow to each vertex were set above a certain constant magnitude. Here, we show the possibility of solving these problems by a simple algorithm even in cases where these magnitudes are different for each vertex.

πŸ“œ SIMILAR VOLUMES

On a realization problem from non-termin
On a realization problem from non-terminal capacity matrices on undirected flow networks
✍ Hiroshi Tamura; Masakazu Sengoku; Shoji Shinoda; Takeo Abe πŸ“‚ Article πŸ“… 2001 πŸ› John Wiley and Sons 🌐 English βš– 309 KB

## Abstract The problem of realizing a given matrix on an undirected flow network has been studied and various results have been obtained. Most of these results consist of necessary and sufficient conditions for methods of realization in which the maximum good flow between the two points and the ma

Note on independence of arcs in antipara
Note on independence of arcs in antiparallel for network flow problems
✍ Jane Nichols Hagstrom πŸ“‚ Article πŸ“… 1984 πŸ› John Wiley and Sons 🌐 English βš– 206 KB πŸ‘ 1 views

## Abstract Given a transportation flow network with two arcs in antiparallel, if the capacities of all other arcs are fixed and the demands at sinks are fixed, at least one of the two arcs will be irrelevant to the problem of flow feasibility. As a consequence, in a stochastic setting, two arcs in

A study on the tie-set graph theory and
A study on the tie-set graph theory and network flow optimization problems
✍ Toshio Koide; Haruki Kubo; Hitoshi Watanabe πŸ“‚ Article πŸ“… 2004 πŸ› John Wiley and Sons 🌐 English βš– 198 KB πŸ‘ 2 views

## Abstract Aiming at establishing a firm basic theory to ring‐based information network management systems, our paper proposes a tie‐set graph theory. We define a binary vector representing a tie‐set in a biconnected undirected graph __G__=(__V__,__E__) as a tie‐set vector. The set of tie‐set vect