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
ABSTRACT
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.
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
ABSTRACT
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.
