Distributed Algorithms to Solve the FOP Issues on the Weighted Convex-Split Networks

DOI

10.2991/jcis.2006.230How to use a DOI?

Keywords

undirected network, directed network, FOP, convex-split network.

Abstract

This paper discusses the Flow-Orientation Problem (FOP), which assigns orientations of all links of an undirected network to obtain a directed network for meeting some flow optimization measurements. First, we describe the background and define three related FOP issues: MDFOP, MDSFOP, and MDDFOP. We discuss the complexity of the FOP on general networks, and also list the essences of convex-split networks. These networks are to be either un-weighted or weighted. Then, we propose the algorithm for solving the MDFOP issue on weighted convex-split networks. Similarly, we can extend the MDFOP approach to solve the MDSFOP and MDDFOP issues. Suppose that  is any flow-orientation of a network N. Let (Г) and u(Г) be the maximum out-degree and the minimum out-degree, respectively, when N is un-weighted. In another, let ε(Г) = maxxV {C(v) + ∑(z,x),z→xW(z,x)}, (Г)=minxV{C(v) + ∑(z,x),z→xW(z,x)}, and Q(Г) = ∑x,yV{(C(x) + ∑x→zW(x,z))-(C(y) + ∑y→zW(y,z))} when N is weighted. The main purpose of various FOP issues is to minimize (Г) - u(Г), ε(Г) - (), Q(Г). Finally, our findings can be applied to enhance performance of link flow and load balancing on networks.

Copyright

© 2006, the Authors. Published by Atlantis Press.

Open Access

This is an open access article distributed under the CC BY-NC license (http://creativecommons.org/licenses/by-nc/4.0/).

Download article (PDF)

TY  - CONF
AU  - Shin-Jer Yang
AU  - Tzu-Chi Guo
PY  - 2006/10
DA  - 2006/10
TI  - Distributed Algorithms to Solve the FOP Issues on the Weighted Convex-Split Networks
BT  - Proceedings of the 9th Joint International Conference on Information Sciences (JCIS-06)
PB  - Atlantis Press
SP  - 368
EP  - 372
SN  - 1951-6851
UR  - https://doi.org/10.2991/jcis.2006.230
DO  - 10.2991/jcis.2006.230
ID  - Yang2006/10
ER  -