Atlantis Press Paper Details: Distributed Algorithms to Solve the FOP Issues on the Weighted Convex-Split Networks

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.


title:		Distributed Algorithms to Solve the FOP Issues on the Weighted Convex-Split Networks
publication:		JCIS-2006 Proceedings
part of series:		Advances in Intelligent Systems Research
ISBN:		978-90-78677-01-7
ISSN:		1951-6851
DOI:		doi:10.2991/jcis.2006.230 (how to use a DOI)
author(s):		Shin-Jer Yang, Tzu-Chi Guo
corresponding author:		Shin-Jer Yang
publication date:		October 2006
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:		© Atlantis Press. This article is distributed under the terms of the Creative Commons Attribution License, which permits non-commercial use, distribution and reproduction in any medium, provided the original work is properly cited.
full text:		JCIS06-CSI-26.pdf (312 K)