Towards Generating Hop-constrained s-t Simple Path Graphs

Summary: Formalizes k-hop-constrained s-t simple path graphs; NP-hard on directed graphs. Proposes EVE, essential-vertex pruning to yield upper-bound graph in O(k^2|E|), verify rest for exact results; experiments on 15 networks show major speedups over baselines and boost hop-constrained path enumeration. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 6564
Venue: SIGMOD
Year: 2023
Pagerank: 4.4718257e-05
Overall Rank: 8,668 | 39.70%
DOI: 10.1145/3588915

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
9,089	Efficient Distributed Hop-Constrained Path Enumeration on Large-Scale Graphs	2024	SIGMOD	4.39898e-05
10,467	Accelerating Skyline Path Enumeration with a Core Attribute Index on Multi-attribute Graphs	2025	SIGMOD	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 8 of 8 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,394	Real-time Constrained Cycle Detection in Large Dynamic Graphs	2018	VLDB	0.0001221552
1,880	TF-Label: a Topological-Folding Labeling Scheme for Reachability Querying in a Large Graph	2013	SIGMOD	0.00010226347
2,756	K-Reach: Who is in Your Small World	2012	VLDB	8.1682536e-05
3,715	Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries	2020	VLDB	6.8220943e-05
4,534	Hop-constrained s-t Simple Path Enumeration: Towards Bridging Theory and Practice	2020	VLDB	6.1049756e-05
6,138	Query-by-Sketch: Scaling Shortest Path Graph Queries on Very Large Networks	2021	SIGMOD	5.1915368e-05
6,208	PathEnum: Towards Real-Time Hop-Constrained s-t Path Enumeration	2021	SIGMOD	5.1568586e-05
6,795	Answering Billion-Scale Label-Constrained Reachability Queries within Microsecond	2020	VLDB	4.9242446e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
11,014	Efficient Regular Simple Path Queries under Transitive Restricted Expressions	2024	VLDB	4.1945683e-05
4,270	Efficient k-Clique Listing: An Edge-Oriented Branching Strategy	2024	SIGMOD	6.3067205e-05
4,430	Finding the Cost-Optimal Path with Time Constraint over Time-Dependent Graphs	2014	VLDB	6.1942479e-05
6,207	Efficiently Computing k-Edge Connected Components via Graph Decomposition	2013	SIGMOD	5.1572428e-05
4,973	Constrained Shortest Path Query in a Large Time-Dependent Graph	2019	VLDB	5.7909705e-05
9,089	Efficient Distributed Hop-Constrained Path Enumeration on Large-Scale Graphs	2024	SIGMOD	4.39898e-05
2,766	On k-Path Covers and their Applications	2014	VLDB	8.1526804e-05
7,675	Distributed Hop-Constrained s-t Simple Path Enumeration at Billion Scale	2022	VLDB	4.6817479e-05
6,208	PathEnum: Towards Real-Time Hop-Constrained s-t Path Enumeration	2021	SIGMOD	5.1568586e-05
4,534	Hop-constrained s-t Simple Path Enumeration: Towards Bridging Theory and Practice	2020	VLDB	6.1049756e-05