Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Pattern Recognition in Embedded Systems: An Overview Read chapter Read first chapter

2015 | OriginalPaper | Chapter

Restricted Shortest Path in Temporal Graphs

Authors : Sudip Biswas, Arnab Ganguly, Rahul Shah

Published in: Database and Expert Systems Applications

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

The restricted shortest path (RSP) problem on directed networks is a well-studied problem, and has a large number of applications such as in Quality of Service routing. The problem is known to be NP-hard. In certain cases, however, the network is not static i.e., edge parameters vary over time. In light of this, we extend the RSP problem for general networks to that for temporal networks. We present several exact algorithms for this problem, one of which uses heuristics, and is similar to the \(A^*\) algorithm. We experimentally evaluate these algorithms by simulating them on both existing temporal networks, and synthetic ones. Furthermore, based on one of the pseudo-polynomial exact algorithms, we derive a fully polynomial time approximation scheme.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter Pattern Recognition in Embedded Systems: An Overview
next chapter An Efficient Distributed Index for Geospatial Databases
Literature
1.
Cai, X., Kloks, T., Wong, C.K.: Time-varying shortest path problems with constraints. Networks 29(3), 141–150 (1997)MathSciNetCrossRef
2.
Carlyle, W.M., Royset, J.O., Kevin Wood, R.: Lagrangian relaxation and enumeration for solving constrained shortest-path problems. Networks 52(4), 256–270 (2008)MathSciNetCrossRef
3.
Day, P.R., Ryan, D.M.: Flight attendant rostering for short-haul airline operations. Oper. Res. 45(5), 649–661 (1997)CrossRef
4.
Ergun, F., Sinha, R., Zhang, L.: An improved FPTAS for restricted shortest path. Inf. Process. Lett. 83(5), 287–291 (2002)MathSciNetCrossRef
5.
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman and Co., New York (1979)
6.
Goldberg, A.V., Harrelson, C.: Computing the shortest path: a search meets graph theory. In: Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2005, pp. 156–165. Society for Industrial and Applied Mathematics, Philadelphia (2005)
7.
Hart, P., Nilsson, N., Raphael, B.: A formal basis for the heuristic determination of minimum cost paths. IEEE Trans. Syst. Sci. Cybern. 4(2), 100–107 (1968)CrossRef
8.
9.
Kempe, D., Kleinberg, J.M., Demers, A.J.: Spatial gossip and resource location protocols. In: Proceedings on 33rd Annual ACM Symposium on Theory of Computing, Heraklion, Crete, Greece, 6–8 July 2001, pp. 163–172 (2001)
10.
Korkmaz, T., Krunz, M.: Multi-constrained optimal path selection. In: Proceedings IEEE INFOCOM 2001, The Conference on Computer Communications, Twentieth Annual Joint Conference of the IEEE Computer and Communications Societies, Twenty Years into the Communications Odyssey, Anchorage, Alaska, USA, 22–26 April 2001, pp. 834–843 (2001)
11.
Li, Y., Harms, J., Holte, R.: Fast exact multiconstraint shortest path algorithms. In: IEEE International Conference on Communications, ICC 2007, June 2007, pp. 123–130 (2007)
12.
Lorenz, D., Orda, A.: QoS routing in networks with uncertain parameters. IEEE/ACM Trans. Netw. 6(6), 768–778 (1998)CrossRef
13.
Lorenz, D.H., Raz, D.: A simple efficient approximation scheme for the restricted shortest path problem. Oper. Res. Lett. 28(5), 213–219 (2001)MathSciNetCrossRef
14.
Mertzios, G.B., Michail, O., Chatzigiannakis, I., Spirakis, P.G.: Temporal network optimization subject to connectivity constraints. In: Fomin, F.V., Freivalds, R., Kwiatkowska, M., Peleg, D. (eds.) ICALP 2013, Part II. LNCS, vol. 7966, pp. 657–668. Springer, Heidelberg (2013) CrossRef
15.
Michail, O., Spirakis, P.G.: Traveling salesman problems in temporal graphs. In: Csuhaj-Varjú, E., Dietzfelbinger, M., Ésik, Z. (eds.) MFCS 2014, Part II. LNCS, vol. 8635, pp. 553–564. Springer, Heidelberg (2014)
16.
Nachtigall, K.: Time depending shortest-path problems with applications to railway networks. Eur. J. Oper. Res. 83(1), 154–166 (1995)CrossRef
17.
Van Mieghem, P., Kuipers, F.: Concepts of exact QoS routing algorithms. IEEE/ACM Trans. Netw. 12(5), 851–864 (2004)CrossRef
18.
Wu, H., Cheng, J., Huang, S., Ke, Y., Lu, Y., Xu, Y.: Path problems in temporal graphs. Proc. VLDB Endow. 7(9), 721–732 (2014)CrossRef
Metadata
Title
Restricted Shortest Path in Temporal Graphs
Authors
Sudip Biswas
Arnab Ganguly
Rahul Shah
Copyright Year
2015
Book
Database and Expert Systems Applications

Print ISBN: 978-3-319-22848-8

Electronic ISBN: 978-3-319-22849-5

Copyright Year: 2015

DOI
https://doi.org/10.1007/978-3-319-22849-5_2

Premium Partner

    Image Credits