Consider a network $$\mathcal{N}$$ =(G, c, τ) whereG=(N, A) is directed graph andc ij andτ , respectively, denote the capacity and transmission time of arc (i, j) ∈A. The quickest flow problem then to determine for given valueυ minimum numberT(υ) units that are necessary transmit (send)υ in from sources sinks′. In this paper we show closely related maximum dynamic linear fractional programming problems. Based on these relationships develop several polynomial algorithms strongly algorithm...

Abstract A dynamic network consists of a directed graph with capacities, costs, and integral transit times on the arcs. In minimum‐cost flow problem (MCDFP), goal is to compute, for given source s , sink t two integers v T feasible from value obeying time bound having minimum total cost. MCDFP contains as subproblems maximum problem, where fixed amount that can be sent within quickest needed sending units . We first prove both are NP‐hard even two‐terminal series‐parallel graphs unit...

Abstract This article presents a fast algorithm for class of parametric assignment problems. Moreover, it is shown how this can be applied to problem arising in the so‐called max‐algebra which results as an analogue classical linear algebra by replacing addition and multiplication ⊕ b = max( , ) ⊗ + respectively. An instance given bipartite graph G ( U V E with 2 n vertices, m edges affine‐linear edge weights c λ i j − )λ ∈ . The task find minimum weight respect all values λ. We develop...

In this paper we investigate scheduling problems which stem from real-world applications in the chemical process industry both a theoretical and practical point of view. After providing survey general mixed integer programming model, present some results on complexity problem important special cases. (We prove NP-hardness polynomial solvability for specially structured cases.) Furthermore, suggest new heuristic approach compare to other heuristics known literature.

In most of the known polynomially solvable cases symmetric travelling salesman problem (TSP) which result from restrictions on underlying distance matrices, have form so-called four-point conditions (the inequalities involve four cities). this paper we treat all possible (symmetric) and investigate whether corresponding TSP can be solved in polynomial time. As a by-product our classification obtain new families exponential neighborhoods for searched time matrix formulated so that search an...

This paper presents a unified approach for bottleneck capacity expansion problems. In the problem, BCEP, we are given finite ground set E, family F of feasible subsets E and nonnegative real ĉe all e ∈ E. Moreover, monotone increasing cost functions fe elements as well budget B. The task is to determine new capacities ce ≥ such that objective function by maxF∈Fmine∈Fce maximized under side constraint overall does not exceed We introduce an algebraic model defining formulating constraint....

In most of the known polynomially solvable cases symmetric travelling salesman problem (TSP) which result from restrictions on underlying distance matrices, have form so-called four-point conditions (the inequalities involve four cities). this paper we treat all possible (symmetric) and investigate whether corresponding TSP can be solved in polynomial time. As a by-product our classification obtain new families exponential neighborhoods for searched time matrix formulated so that search an...