Document Zbl 0485.90081

A network flow solution to some nonlinear 0-1 programming problems, with application to graph theory. (English) Zbl 0485.90081

Networks 12, 141-159 (1982).

Page: −5 −4 −3 −2 −1 ±0 +1 +2 +3 +4 +5 Show Scanned Page
scan of Zbl 0485.90081

MSC:

90C35	Programming involving graphs or networks
90C09	Boolean programming
90B10	Deterministic network models in operations research
90C30	Nonlinear programming
65K05	Numerical mathematical programming methods
05C35	Extremal problems in graph theory
90B35	Deterministic scheduling theory in operations research
91B06	Decision theory

Keywords:

network flow technique; unconstrained nonlinear 0-1 programming; ratio of two polynomials; investment selection; sequence of minimum-cut problems; bounding scheme; maximum-clique; vertex packing

Cite Review PDF

Full Text: DOI

References:

[1]	Balinski, Management Sci. 17 pp 230– (1970)
[2]	Graphs and Hypergraphs. North-Holland, Amsterdam (1973).
[3]	and , Network flows and generalized path compression. In Proceedings, ACM Symposium on the Theory of Computing (1979) Vol. 11, pp. 13–26.
[4]	and , Flows in Networks. Princeton Univ. Press, Princeton, NJ (1962).
[5]	Hammer, Operations Res. 13 pp 388– (1965)
[6]	and , Boolean Methods in Operations Research. Springer, New York (1968). · doi:10.1007/978-3-642-85823-9
[7]	Programmes mathématiques en variables 0-1. Thèse, Université Libre de Bruxelles, Belgique (1974).
[8]	Graph Theory. Addison-Wesley, Reading, MA (1969).
[9]	Karzanov, Sov. Math. Dokl. 15 pp 434– (1974)
[10]	Combinatorial Optimization: Networks and Matroids. Holt, Rinehart and Winston, New York (1976). · Zbl 0413.90040
[11]	Lawler, Ann. Discrete Math. 2 pp 75– (1978)
[12]	Nash-Williams, J. London Math. Soc. 36 pp 445– (1961)
[13]	Picard, Management Sci. 22 pp 1268– (1976)
[14]	Picard, Operations Res. 21 pp 261– (1973)
[15]	Picard, Networks 5 pp 357– (1974)
[16]	and , Networks, Graphs and Some Non-Linear 0-1 Programming Problems. Technical Report EP77-R-32, Ecole Polytechnique de Montréal (1977).
[17]	Rhys, Management Sci. 17 pp 200– (1970)
[18]	An O(nI log2 I)Maximum Flow Algorithm. Technical Report STAN-CS-702-78, Computer Science Department, Stanford University (1978).
[19]	Sidney, Operations Res. 23 pp 283– (1975)

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.