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: 6565
Venue: SIGMOD
Year: 2023
Pagerank: 4.467539e-05
Overall Rank: 8,666 | 39.78%
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,086	Efficient Distributed Hop-Constrained Path Enumeration on Large-Scale Graphs	2024	SIGMOD	4.3947639e-05
10,477	Accelerating Skyline Path Enumeration with a Core Attribute Index on Multi-attribute Graphs	2025	SIGMOD	4.1905499e-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,392	Real-time Constrained Cycle Detection in Large Dynamic Graphs	2018	VLDB	0.00012224015
1,879	TF-Label: a Topological-Folding Labeling Scheme for Reachability Querying in a Large Graph	2013	SIGMOD	0.00010227906
2,762	K-Reach: Who is in Your Small World	2012	VLDB	8.1614818e-05
3,702	Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries	2020	VLDB	6.8251643e-05
4,536	Hop-constrained s-t Simple Path Enumeration: Towards Bridging Theory and Practice	2020	VLDB	6.099154e-05
6,144	Query-by-Sketch: Scaling Shortest Path Graph Queries on Very Large Networks	2021	SIGMOD	5.1865526e-05
6,207	PathEnum: Towards Real-Time Hop-Constrained s-t Path Enumeration	2021	SIGMOD	5.1519085e-05
6,796	Answering Billion-Scale Label-Constrained Reachability Queries within Microsecond	2020	VLDB	4.9195203e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
11,017	Efficient Regular Simple Path Queries under Transitive Restricted Expressions	2024	VLDB	4.1905499e-05
4,266	Efficient k-Clique Listing: An Edge-Oriented Branching Strategy	2024	SIGMOD	6.3006582e-05
4,429	Finding the Cost-Optimal Path with Time Constraint over Time-Dependent Graphs	2014	VLDB	6.1882774e-05
6,206	Efficiently Computing k-Edge Connected Components via Graph Decomposition	2013	SIGMOD	5.1522897e-05
4,976	Constrained Shortest Path Query in a Large Time-Dependent Graph	2019	VLDB	5.7854051e-05
9,086	Efficient Distributed Hop-Constrained Path Enumeration on Large-Scale Graphs	2024	SIGMOD	4.3947639e-05
2,773	On k-Path Covers and their Applications	2014	VLDB	8.1447894e-05
7,674	Distributed Hop-Constrained s-t Simple Path Enumeration at Billion Scale	2022	VLDB	4.677258e-05
6,207	PathEnum: Towards Real-Time Hop-Constrained s-t Path Enumeration	2021	SIGMOD	5.1519085e-05
4,536	Hop-constrained s-t Simple Path Enumeration: Towards Bridging Theory and Practice	2020	VLDB	6.099154e-05