{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T03:09:19Z","timestamp":1761620959339},"reference-count":26,"publisher":"Wiley","issue":"5","license":[{"start":{"date-parts":[[2006,10,11]],"date-time":"2006-10-11T00:00:00Z","timestamp":1160524800000},"content-version":"vor","delay-in-days":4454,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Networks"],"published-print":{"date-parts":[[1994,8]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We extend the qualitative theory of sensitivity analysis for minimum\u2010cost flow problems developed by Granot and Veinott to minimum\u2010cost flow problems with one additional linear constraint. Two natural extensions of the \u201cless dependent on\u201d partial ordering of the arcs are presented. One is decidable in linear time, whereas the other yields more information but is NP\u2010complete in general. The Ripple Theorem gives upper bounds on the absolute value of optimal\u2010flow variations as a function of variations in the problem parameters. The theory of substitutes and complements presents necessary and sufficient conditions for optimal\u2010flow changes to consistently have the same (or the opposite) sign in two given arcs. The Monotonicity Theory links the changes in the value of the parameters to the change in the optimal arc\u2010flows, and bounds on the rates of changes are discussed. The departure from the pure network structure is shown to have a profound effect on computational issues. Indeed, the complexity of determining substitutes and complements, although linear for the unconstrained (no additional constraint) case, is shown to be NP\u2010complete in general for the constrained case. However, for all intractable problems, families of cases arise from easily recognizable graph structures which can be computed in linear time. \u00a9 1994 by John Wiley &amp; Sons, Inc.<\/jats:p>","DOI":"10.1002\/net.3230240505","type":"journal-article","created":{"date-parts":[[2007,5,12]],"date-time":"2007-05-12T18:21:31Z","timestamp":1178994091000},"page":"285-296","source":"Crossref","is-referenced-by-count":3,"title":["Ripples, complements, and substitutes in singly constrained monotropic parametric network flow problems"],"prefix":"10.1002","volume":"24","author":[{"given":"Antoine","family":"Gautier","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Frieda","family":"Granot","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"311","published-online":{"date-parts":[[2006,10,11]]},"reference":[{"key":"e_1_2_1_2_2","volume-title":"The Design and Analysis of Computer Algorithms","author":"Aho A.","year":"1974"},{"key":"e_1_2_1_3_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.37.1.118"},{"key":"e_1_2_1_4_2","doi-asserted-by":"publisher","DOI":"10.1016\/0305-0548(88)90022-6"},{"key":"e_1_2_1_5_2","doi-asserted-by":"crossref","unstructured":"D. P.Bertsekas A new algorithm for solution of restrictive networks involving diodes.IEEE Trans. Circuit Syst.CAS\u201023 (1976)599\u2013608.","DOI":"10.1109\/TCS.1976.1084140"},{"key":"e_1_2_1_6_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230070105"},{"key":"e_1_2_1_7_2","volume-title":"Algebraic Theory of Lattices","author":"Crawley P.","year":"1973"},{"key":"e_1_2_1_8_2","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0120941"},{"key":"e_1_2_1_9_2","volume-title":"Computers and Intractability: A guide to NP\u2010completeness","author":"Garey M. R.","year":"1979"},{"key":"e_1_2_1_10_2","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6377(92)90003-L"},{"key":"e_1_2_1_11_2","article-title":"On the equivalence of constrained and unconstrained flows","author":"Gautier A.","journal-title":"Discr. Appl. Math."},{"key":"e_1_2_1_12_2","article-title":"A parametric analysis of a constrained nonlinear inventory\u2010production model","author":"Gautier A.","journal-title":"Management Sci."},{"key":"e_1_2_1_13_2","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.12.4.277"},{"key":"e_1_2_1_14_2","doi-asserted-by":"publisher","DOI":"10.1287\/moor.10.3.471"},{"key":"e_1_2_1_15_2","unstructured":"R. V.HelgasonandJ. L.Kennington An Efficient Specialization of the Convex Simplex Method for Nonlinear Network Flow Problems. Technical Report IEOR 99017 Southern Methodist University (1977)."},{"key":"e_1_2_1_16_2","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.23.7.737"},{"key":"e_1_2_1_17_2","unstructured":"J. B.Orlin Minimum convex cost dynamic network flows. Working Paper Sloan School of Management M.I.T. (1982)."},{"key":"e_1_2_1_18_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01585655"},{"key":"e_1_2_1_19_2","volume-title":"Combinatorial Optimization; Algorithms and Complexity","author":"Papadimitriou C. H.","year":"1982"},{"key":"e_1_2_1_20_2","unstructured":"J. S.Provan Substitutes and Complements in Constrained Linear Models. Technical Report #UNC\/ORSA\/TR\u201086\/23 Curriculum in Operations Research and Systems Analysis University of North Carolina at Chapel Hill (December1986)."},{"key":"e_1_2_1_21_2","first-page":"104","volume-title":"Combinatorial Mathematics and Its Applications, Proceedings of the Chapel Hill Conference","author":"Rockafellar R. T.","year":"1967"},{"key":"e_1_2_1_22_2","volume-title":"Network Flows and Monotropic Optimization","author":"Rockafellar R. T.","year":"1984"},{"key":"e_1_2_1_23_2","unstructured":"S. B.SpaltiandT. H.Liebling A special case of a network problem with one side constraint. Working Paper R.O. 890429 D\u00e9partment de Math\u00e9ematiques EPF Lausanne Switzerland (1989)."},{"key":"e_1_2_1_24_2","doi-asserted-by":"publisher","DOI":"10.3138\/9781487584863"},{"key":"e_1_2_1_25_2","unstructured":"A. F.Veinott Monotone solutions of extremal problems unpublished (1965)."},{"key":"e_1_2_1_26_2","unstructured":"A. F.Veinott Lattice programming forthcoming."},{"key":"e_1_2_1_27_2","doi-asserted-by":"crossref","first-page":"339","DOI":"10.1090\/S0002-9947-1932-1501641-2","article-title":"Non separable and planar graphs","volume":"34","author":"Whitney H.","year":"1932","journal-title":"Trans. Am. Math. Soc."}],"container-title":["Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fnet.3230240505","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/net.3230240505","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,24]],"date-time":"2023-10-24T21:53:04Z","timestamp":1698184384000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/net.3230240505"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994,8]]},"references-count":26,"journal-issue":{"issue":"5","published-print":{"date-parts":[[1994,8]]}},"alternative-id":["10.1002\/net.3230240505"],"URL":"https:\/\/doi.org\/10.1002\/net.3230240505","archive":["Portico"],"relation":{},"ISSN":["0028-3045","1097-0037"],"issn-type":[{"value":"0028-3045","type":"print"},{"value":"1097-0037","type":"electronic"}],"subject":[],"published":{"date-parts":[[1994,8]]}}}