ADJACENT EXTREME FLOWS AND APPLICATION TO MIN CONCAVE COST FLOW PROBLEMS

被引：26

作者：

GALLO, G

SODINI, C

机构：

[1] Consiglio Nazionale Delle Ricerche, Pisa

来源：

NETWORKS | 1979年 / 9卷 / 02期

关键词：

D O I：

10.1002/net.3230090202

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

In this paper an algorithm is presented which, given an extreme flow on a Network, enumerates all its neighboring extreme flows. The algorithm is based on a graph theoretic characterization of the adjacency relationship. The relevance of finding the set of extreme flows adjacent to a given one is discussed from the point of view of concave optimization on Networks. Copyright © 1979 Wiley Periodicals, Inc., A Wiley Company

引用

页码：95 / 121

页数：27

共 14 条

[1] Dantzig G.G., Linear Programming and Extension, (1963)
[2] Florian M., Rossin Arthiat M., De Werra D., A Property of Minimum Concave Cost Flows in Capacitated Networks, Can J.O.R., 9, pp. 293-304, (1971)
[3] Gallo G., Sodini C.
[4] Tui, Concave Programming under Linear Constraints, Soviet Mathematics, 5, pp. 1437-1440, (1964)
[5] Johnson E.L., Networks and Basic solutions, Operations Research, 14, pp. 619-623, (1966)
[6] Murty K.G., Solving the Fixed Charge Problem by Ranking the Extreme Points, Operations Research, 16, pp. 268-279, (1968)
[7] Murty K.G., Linear and Combinatorial Programming, (1976)
[8] Read R.C., Tarjan R.E., Bounds on Backtrack Algorithms for Listing Cycles, Paths and Spanning Trees, Networks, 5, pp. 237-252, (1975)
[9] Roy B., (1970)
[10] Taha H.A., Concave Minimization over a Convex Polyhedron, Naval Res. Log. Quarterly, 20, pp. 533-548, (1973)

← 1 2 →