Solving the MCQP, MLT, and MMLT problems and computing weakly and strongly stable quickest paths

The quickest path problem consists of finding a path in a directed network to transmit a given amount $$\sigma $$ σ of items from a source node to a sink node with minimal transmission time, where the transmission time depends on the traversal times $$\tau $$ τ and the capacities u of the arcs. We suppose that there exist more than one quickest path and finds a quickest path with a special property. In this paper, first, some algorithms to find a quickest path with minimum capacity, minimum lead time, and min-max arc lead time are presented, which runs in $$O(r(m+n \log n))$$ O ( r ( m + n log n ) ) and $$ O((r(m+n \log n))\log r') $$ O ( ( r ( m + n log n ) ) log r ′ ) time, where r and $$ r' $$ r ′ are the number of distinct capacity and lead time values and m and n are the number of arcs and nodes in the given network. Then, we suppose that values $$\sigma , \tau $$ σ , τ and u change to $$\sigma ', \tau '$$ σ ′ , τ ′ , and $$u'$$ u ′ . The purpose is to find a quickest path such that it has the minimum transmission time value among all quickest paths, by changing $$\sigma $$ σ to $$\sigma '$$ σ ′ , $$\tau $$ τ to $$\tau '$$ τ ′ , or u to $$u'$$ u ′ . We show that some of these problems are solved in strongly polynomial time and the others remain as open problems.