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

Mehdi Ghiyasvand () and Azam Ramezanipour ()
Additional contact information
Mehdi Ghiyasvand: Bu-Ali Sina University
Azam Ramezanipour: Bu-Ali Sina University

Telecommunication Systems: Modelling, Analysis, Design and Management, 2018, vol. 68, issue 2, No 7, 217-230

Abstract: 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))$$ 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.

Keywords: Quickest path; Transmission time; Bicriteria problem; Shortest path; Nondominated path (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s11235-017-0388-y Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:telsys:v:68:y:2018:i:2:d:10.1007_s11235-017-0388-y

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/11235

DOI: 10.1007/s11235-017-0388-y

Access Statistics for this article

Telecommunication Systems: Modelling, Analysis, Design and Management is currently edited by Muhammad Khan

More articles in Telecommunication Systems: Modelling, Analysis, Design and Management from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().