Advanced search
Publication Cover
International Journal of Parallel, Emergent and Distributed Systems Volume 37, 2022 - Issue 4
Submit an article Journal homepage
46
Views
0
CrossRef citations to date
0
Altmetric
Research Article

Minsum node-disjoint paths with time-varying delay functions

Xiaohong XueCollege of Mathematics, Taiyuan University of Technology, Taiyuan, Shanxi, People's Republic of ChinaORCID Iconhttps://orcid.org/0000-0001-6898-7444View further author information
ORCID Icon &
Shurong ZhangCollege of Mathematics, Taiyuan University of Technology, Taiyuan, Shanxi, People's Republic of ChinaCorrespondence[email protected]
ORCID Iconhttps://orcid.org/0000-0002-0452-7761View further author information
ORCID Icon
Pages 398-412 | Received 26 Dec 2021, Accepted 28 Dec 2021, Published online: 09 Jan 2022

References

  • Bruera F, Cicerone S, D'Angelo G, et al. Dynamic multi-level overlay graphs for shortest paths. Math Comput Sci. 2008;1(4):709–736.
  • Delling D, Wagner D. Landmark-based routing in dynamic graphs. WEA'07 Proc 6th Int Conf Exp Algorithms. 2007;4525:52–65.
  • Narvez P, Siu K-Y, Tzeng H-Y. New dynamic algorithms for shortest path tree computation. IEEE ACM Trans Netw. 2000;8(6):734–746.
  • Wagner D, Wattenhofer R. Algorithms for Sensor and Ad Hoc Networks. Berlin Heidelberg: Springer-Verlag; 2007. p. 1–35.
  • Fleischer R, Ge Q, Li J, et al. Efficient algorithms for k-disjoint paths problems on DAGs June 6-8 USA International Conference on Algorithmic Aspects in Information and Management 2007.
  • Suurballe JW. Disjoint paths in a network. Networks. 1974;4(2):125–145.
  • Ahuja RK, Magnanti TL, Orlin JB. Network flows, theory, algorithms, and applications. Englewood Cliffs: Prentice Hall; 1993.
  • Suurballe JW, Tarjan RE. A quick method for finding shortest pairs of disjoint paths. Networks. 1984;14(2):325–336.
  • Li C-L, McCormick TS, Simich-Levi D. The complexity of finding two disjoint paths with min-max objective function. Discrete Appl Math. 1990;26(1):105–115.
  • Yu C-C, Lin C-H, Wang B-F. Improved algorithms for finding length-bounded two vertex-disjoint paths in a planar graph and minmax k vertex-disjoint paths in a directed acyclic graph. J Comput Syst Sci. 2010;76(8):697–708.
  • Wu BY. A note on approximating the min-max vertex disjoint paths on directed acyclic graphs. J Comput Syst Sci. 2011;77(6):1054–1057.
  • Fortune S, Hopcroft JE, Wyllie JC. The directed subgraph homeomorphism problem. Theor Comput Sci. 1980;10(2):111–121.
  • Yang B, Zheng SQ, Katukam S. Finding two disjoint paths in a network with min-min objective function. Nov 3-5. USA. Fifteenth IASTED International Conference on Parallel and Distributed Computing and Systems. 2003.
  • Cooke KL, Halsey E. The shortest route through a network with time-dependent internodal transit times. J Math Anal Appl. 1966;14(3):493–498.
  • Dreyfus SE. An appraisal of some shortest-path algorithms. Oper Res. 1969;17(3):395–412.
  • Dijkstra EW. A note on two problems in connexion with graphs. Numer Math. 1959;1(1):269–271.
  • Orda A, Rom R. Shortest-path and minimum-delay algorithms in networks with time-dependent edge-length. J ACM. 1990;37(3):607–625.
  • Kaufman DE, Smith RL. Fastest paths in time-dependent networks for intelligent vehicle-highway systems application. J Intell Transp Syst. 1993;1(1):1–11.
  • Ding B, Yu JX, Qin L. Finding time-dependent shortest paths over large graphs. Mar. 25-30. France. The 11th International Conference on Extending Database Technology. 2008.
  • Foschini L, Hershberger J, Suri S. On the complexity of time-dependent shortest paths. Algorithmica. 2014;68(4):1075–1097.
  • Li L, Wang S, Zhou X. Time-dependent hop labeling on road network. Apr. 8-11. China. International Conference on Data Engineering. 2019.
  • Wang Y, Li G, Tang N. Querying shortest paths on time dependent road networks. Proc VLDB Endow. 2019;12(11):1249–1261.

Reprints and Corporate Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

To request a reprint or corporate permissions for this article, please click on the relevant link below:

Order Reprints Request Corporate Permissions

Academic Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

Obtain permissions instantly via Rightslink by clicking on the button below:

Request Academic Permissions

If you are unable to obtain permissions via Rightslink, please complete and submit this Permissions form. For more information, please visit our Permissions help page.

Related research

People also read lists articles that other readers of this article have read.

Recommended articles lists articles that we recommend and is powered by our AI driven recommendation engine.

Cited by lists all citing articles based on Crossref citations.
Articles with the Crossref icon will open in a new tab.