Premium
Substitutes, complements, and ripples in multicommodity flows on suspension graphs
Author(s) -
CiurriaInfosino Iara,
Granot Frieda,
Veinott Arthur F.
Publication year - 2014
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.21557
Subject(s) - multi commodity flow problem , mathematics , graph , enumeration , flow network , combinatorics , suspension (topology) , flow (mathematics) , discrete mathematics , mathematical optimization , pure mathematics , geometry , homotopy
We examine in this article when it is possible to predict, without numerical computation, the direction of change of optimal multicommodity flows on suspension graphs resulting from changes in arc‐commodity parameters. Using results of Evans (Oper Res 26 (1978), 673–679) and of Soun and Truemper (SIAM J Algebr Discrete Meth 1 (1980), 348–358), the multicommodity flow problem on a graph that is two‐isomorphic to a suspension graph is reduced to a single‐commodity flow problem on an enlarged graph, called a “rolodex graph.” Such a reduction allows us to apply results of Granot and Veinott (Math Oper Res 10 (1985), 471–497), developed for single‐commodity network‐flow problems, to derive qualitative sensitivity analysis results for multicommodity flow problems on graphs which are two‐isomorphic to suspension graphs. © 2014 Wiley Periodicals, Inc. NETWORKS, Vol. 64(2), 65–75 2014