In 2013, Orlin proved that the max flow problem could be solved in O(nm) time. His algorithm was the fastest for very sparse graphs. If the graph was not sufficiently sparse, the fastest running time was an algorithm due to King, Rao, and Tarjan. We describe a new variant of the excess scaling algorithm for … Read more
This paper presents a new method for identifying critical nodes in planar networks. We propose an efficient method to evaluate the quality of solutions by using special properties of planar networks. It enables us to develop a computationally efficient heuristic algorithm for the problem. The proposed algorithm assisted on randomly generated planar networks. The experimental … Read more
In the last decades, research on emergency traffic management has received high attention from the operations research community and many pioneer researchers have established it as one of the most fertile research areas. We consider the computationally hard flows over time problems from wider perspective including flow/time dependent attributes (dynamic flows), a possibility of flows … Read more
The contraflow techniques have widely been effective in evacuation planning research. We present effcient algorithms to solve the evacuation network flow problems, namely, the maximum, earliest arrival, quickest and lex-maximum dynamic contraflow problems having constant attributes and their generalizations with partial contraflow recon guration. Moreover, the contraflow models with inflow dependent and load dependent transit times … Read more
We develop a fast method to compute an optimal robust shortest path in large networks like road networks, a fundamental problem in traffic and logistics under uncertainty. In the robust shortest path problem we are given an $s$-$t$-graph $D(V,A)$ and for each arc a nominal length $c(a)$ and a maximal increase $d(a)$ of its length. … Read more
Two nodes of a wireless network may not be able to communicate with each other directly perhaps due to obstacles or insufficient signal strength. This necessitates the use of intermediate nodes to relay information. Often, one designates a (preferably small) subset of them to relay these messages (i.e., to serve as a virtual backbone for … Read more
We study the robust resource constrained shortest path problem (RCSPP) under uncertainty in cost and multiple resource consumption. Contrary to the deterministic RCSPP where the cost and the consumption of resources on an arc are known and fixed, the robust RCSPP models the case where both the cost and the resource consumption are random, and … Read more
Influence maximization problems aim to identify key players in (social) networks and are typically motivated from viral marketing. In this work, we introduce and study the Generalized Least Cost Influence Problem (GLCIP) that generalizes many previously considered problem variants and allows to overcome some of their limitations. A formulation that is based on the concept … Read more
We study network models where flows cannot be split or merged when passing through certain nodes, i.e., for such nodes, each incoming arc flow must be matched to an outgoing arc flow of identical value. This requirement, which we call “no-split no-merge” (NSNM), appears in railroad applications where train compositions can only be modified at … Read more
The minimization of operation costs for natural gas transport networks is studied. Based on a recently developed model hierarchy ranging from detailed models of instationary partial differential equations with temperature dependence to highly simplified algebraic equations, modeling and discretization error estimates are presented to control the overall error in an optimization method for stationary and … Read more