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: 11806
Venue: VLDB
Year: 2019
Pagerank: 5.7909705e-05
Overall Rank: 4,973 | 65.41%
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
5,250	Architecture-Intact Oracle for Fastest Path and Time Queries on Dynamic Spatial Networks	2020	SIGMOD	5.6044961e-05
6,795	Answering Billion-Scale Label-Constrained Reachability Queries within Microsecond	2020	VLDB	4.9242446e-05
8,242	Hunting Temporal Bumps in Graphs with Dynamic Vertex Properties	2022	SIGMOD	4.551877e-05
10,135	ABFlow: Alert Bursting Flow Query in Streaming Temporal Flow Networks	2026	SIGMOD	4.1945683e-05
10,397	Bursting Flow Query on Large Temporal Flow Networks	2025	SIGMOD	4.1945683e-05
11,199	QHL: A Fast Algorithm for Exact Constrained Shortest Path Search on Road Networks	2023	SIGMOD	4.1945683e-05
11,497	Towards Crowd-aware Indoor Path Planning	2021	VLDB	4.1945683e-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,024	Path Problems in Temporal Graphs	2014	VLDB	0.00014609643
1,555	Efficient Route Planning on Public Transportation Networks: A Labelling Approach	2015	SIGMOD	0.00011395261
3,164	Minimal On-Road Time Route Scheduling on Time-Dependent Graphs	2017	VLDB	7.4543722e-05
4,430	Finding the Cost-Optimal Path with Time Constraint over Time-Dependent Graphs	2014	VLDB	6.1942479e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
11,199	QHL: A Fast Algorithm for Exact Constrained Shortest Path Search on Road Networks	2023	SIGMOD	4.1945683e-05
10,985	Constant-time Connectivity Querying in Dynamic Graphs	2024	SIGMOD	4.1945683e-05
4,970	On Querying Connected Components in Large Temporal Graphs	2023	SIGMOD	5.7945079e-05
5,366	Minimum Spanning Trees in Temporal Graphs	2015	SIGMOD	5.5460085e-05
2,188	Effective Indexing for Approximate Constrained Shortest Path Queries on Large Road Networks	2017	VLDB	9.3372315e-05
3,164	Minimal On-Road Time Route Scheduling on Time-Dependent Graphs	2017	VLDB	7.4543722e-05
9,680	PCSP: Efficiently Answering Label-Constrained Shortest Path Queries in Road Networks	2024	VLDB	4.3047774e-05
1,230	Graph Indexing of Road Networks for Shortest Path Queries with Label Restrictions	2011	VLDB	0.00013150837
1,024	Path Problems in Temporal Graphs	2014	VLDB	0.00014609643
4,430	Finding the Cost-Optimal Path with Time Constraint over Time-Dependent Graphs	2014	VLDB	6.1942479e-05