Constrained Shortest Path Query in a Large Time-Dependent Graph

Summary: Constrained shortest-path queries in large time-dependent graphs; defines PCSP and ICSP. NP-completeness for PCSP and EXPSPACE for ICSP; introduces approximate sequential algorithms and parallel scalable solutions, with real-network experiments confirming efficiency. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 11807
Venue: VLDB
Year: 2019
Pagerank: 6.7642043e-05
Overall Rank: 4,431 | 69.21%
DOI: 10.14778/3339490.3339491

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 7 of 7 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
4,726	Architecture-Intact Oracle for Fastest Path and Time Queries on Dynamic Spatial Networks	2020	SIGMOD	6.6048615e-05
6,504	Answering Billion-Scale Label-Constrained Reachability Queries within Microsecond	2020	VLDB	5.9147772e-05
8,246	Hunting Temporal Bumps in Graphs with Dynamic Vertex Properties	2022	SIGMOD	5.5248738e-05
10,135	ABFlow: Alert Bursting Flow Query in Streaming Temporal Flow Networks	2026	SIGMOD	5.1725247e-05
10,408	Bursting Flow Query on Large Temporal Flow Networks	2025	SIGMOD	5.1725247e-05
11,201	QHL: A Fast Algorithm for Exact Constrained Shortest Path Search on Road Networks	2023	SIGMOD	5.1725247e-05
11,501	Towards Crowd-aware Indoor Path Planning	2021	VLDB	5.1725247e-05

Outgoing Citations (Sorted by Pagerank)

Showing 4 of 4 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
1,127	Path Problems in Temporal Graphs	2014	VLDB	0.00012158287
1,571	Efficient Route Planning on Public Transportation Networks: A Labelling Approach	2015	SIGMOD	0.00010388842
4,070	Minimal On-Road Time Route Scheduling on Time-Dependent Graphs	2017	VLDB	6.9869512e-05
4,469	Finding the Cost-Optimal Path with Time Constraint over Time-Dependent Graphs	2014	VLDB	6.7425063e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
11,201	QHL: A Fast Algorithm for Exact Constrained Shortest Path Search on Road Networks	2023	SIGMOD	5.1725247e-05
10,988	Constant-time Connectivity Querying in Dynamic Graphs	2024	SIGMOD	5.1725247e-05
4,236	On Querying Connected Components in Large Temporal Graphs	2023	SIGMOD	6.8787462e-05
4,992	Minimum Spanning Trees in Temporal Graphs	2015	SIGMOD	6.4789094e-05
2,516	Effective Indexing for Approximate Constrained Shortest Path Queries on Large Road Networks	2017	VLDB	8.5486549e-05
4,070	Minimal On-Road Time Route Scheduling on Time-Dependent Graphs	2017	VLDB	6.9869512e-05
9,664	PCSP: Efficiently Answering Label-Constrained Shortest Path Queries in Road Networks	2024	VLDB	5.2956801e-05
1,252	Graph Indexing of Road Networks for Shortest Path Queries with Label Restrictions	2011	VLDB	0.00011557184
1,127	Path Problems in Temporal Graphs	2014	VLDB	0.00012158287
4,469	Finding the Cost-Optimal Path with Time Constraint over Time-Dependent Graphs	2014	VLDB	6.7425063e-05