NDLI: Shortest Paths in Time-Dependent FIFO Networks

Content Provider	Springer Nature Link
Author	Dehne, Frank Omran, Masoud T. Sack, Jörg Rüdiger
Copyright Year	2010
Abstract	In this paper, we study the time-dependent shortest paths problem for two types of time-dependent FIFO networks. First, we consider networks where the availability of links, given by a set of disjoint time intervals for each link, changes over time. Here, each interval is assigned a non-negative real value which represents the travel time on the link during the corresponding interval. The resulting shortest path problem is the time-dependent shortest path problem for availability intervals ( $\mathcal{TDSP}_{\mathrm{int}}$ ), which asks to compute all shortest paths to any (or all) destination node(s) d for all possible start times at a given source node s. Second, we study time-dependent networks where the cost of using a link is given by a non-decreasing piece-wise linear function of a real-valued argument. Here, each piece-wise linear function represents the travel time on the link based on the time when the link is used. The resulting shortest paths problem is the time-dependent shortest path problem for piece-wise linear functions ( $\mathcal{TDSP}_{\mathrm{lin}}$ ) which asks to compute, for a given source node s and destination d, the shortest paths from s to d, for all possible starting times.We present an algorithm for the $\mathcal{TDSP}_{\mathrm{lin}}$ problem that runs in time O((F d +γ)(\|E\|+\|V\|log \|V\|)) where F d is the output size (i.e., number of linear pieces needed to represent the earliest arrival time function to d) and γ is the input size (i.e., number of linear pieces needed to represent the local earliest arrival time functions for all links in the network). We then solve the $\mathcal{TDSP}_{\mathrm{int}}$ problem in O(λ(\|E\|+\|V\|log \|V\|)) time by reducing it to an instance of the $\mathcal{TDSP}_{\mathrm{lin}}$ problem. Here, λ denotes the total number of availability intervals in the entire network. Both methods improve significantly on the previously known algorithms.
Starting Page	416
Ending Page	435
Page Count	20
File Format	PDF
ISSN	01784617
Journal	Algorithmica
Volume Number	62
Issue Number	1-2
e-ISSN	14320541
Language	English
Publisher	Springer-Verlag
Publisher Date	2010-10-28
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Time-dependent networks Earliest arrival time Shortest paths FIFO property Algorithms Computer Systems Organization and Communication Networks Mathematics of Computing Data Structures, Cryptology and Information Theory Theory of Computation Algorithm Analysis and Problem Complexity
Content Type	Text
Resource Type	Article
Subject	Applied Mathematics Computer Science Applications

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Distance Oracles for Time-Dependent Networks

On the Complexity of Time-Dependent Shortest Paths

Time-Dependent SHARC-Routing

On Dynamic Shortest Paths Problems

A Quadratic Algorithm for Finding Next-to-Shortest Paths in Graphs

All-Pairs Shortest Paths with Real Weights in O(n 3/log n) Time

Engineering a New Algorithm for Distributed Shortest Paths on Dynamic Networks

Computing Approximate Shortest Paths on Convex Polytopes

Finding the k Shortest Paths in Parallel

Shortest Paths in Time-Dependent FIFO Networks

Similar Documents

Distance Oracles for Time-Dependent Networks

On the Complexity of Time-Dependent Shortest Paths

Time-Dependent SHARC-Routing

On Dynamic Shortest Paths Problems

A Quadratic Algorithm for Finding Next-to-Shortest Paths in Graphs

All-Pairs Shortest Paths with Real Weights in O(n 3/log n) Time

Engineering a New Algorithm for Distributed Shortest Paths on Dynamic Networks

Computing Approximate Shortest Paths on Convex Polytopes

Finding the k Shortest Paths in Parallel

Shortest Paths in Time-Dependent FIFO Networks