Advertisement
Published in:
27-09-2017
Solving the MCQP, MLT, and MMLT problems and computing weakly and strongly stable quickest paths
Published in: Telecommunication Systems | Issue 2/2018
Log inActivate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Abstract
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))\) and \( O((r(m+n \log n))\log r') \) time, where r and \( 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'\). 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'\). We show that some of these problems are solved in strongly polynomial time and the others remain as open problems.