Substitutes, complements, and ripples in multicommodity flows on suspension graphs

Substitutes, complements, and ripples in multicommodity flows on suspension graphs

0.00 Avg rating0 Votes
Article ID: iaor201522258
Volume: 64
Issue: 2
Start Page Number: 65
End Page Number: 75
Publication Date: Sep 2014
Journal: Networks
Authors: , ,
Keywords: networks, combinatorial optimization, networks: flow
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.