Academic Journals Database
Disseminating quality controlled scientific knowledge

s-t-Flow on The Network with Hybrid Graph

Author(s): CHENG Cong-dian

Journal: Journal of Chongqing Normal University
ISSN 1672-6693

Volume: 29;
Issue: 1;
Start page: 12;
Date: 2012;
Original page

Keywords: hybrid graph | network | s-t-flow | decomposition | algorithm | maximum flow

Under the framework of hybrid graph, the present work firstly defines the road, path, path system, s-t-flows, path s-t- flows and positive path s-t- flows, etc. on the network, and shows the maximum flow on a path system without cycles to be a positive path s-t- flow. Then this paper designs a polynomial time algorithm to decompose an s-t-flow into a path s-t- flow, as well as prove its feasibility and complexity. Propose and prove a theorem that explains the relation between s-t-flow and the s-t-path flow with the decomposition. Propose and prove the s-t-flow conservation rule between the source and the sink. Finally, it further discusses the transformation between the two kinds of flows, and a few of related problems; in particular, it establishes the formulae for their translating and proves that their value does not change when they translate each other. These works improve and extend the previous corresponding works of Ford and Fulkerson (1962), Korte and Vygen(2000) as well as others.
Affiliate Program     

Tango Jona
Tangokurs Rapperswil-Jona