Minimum Strongly Connected Subgraph Collection in Dynamic Graphs

Summary: Defines MSCSC: find minimum-edge subgraphs that each span a maximal strongly-connected node set; proves NP-hard and targets approximations. Proposes MSC (one-pass, linear-time with guarantees), MSCi (reduced-DAG incrementals) and MSCd (local delete updates) for billion-edge graphs. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 13377
Venue: VLDB
Year: 2024
Pagerank: 4.6696364e-05
Overall Rank: 7,716 | 46.33%
DOI: 10.14778/3648160.3648173

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,311	Efficient Temporal Edge-Core Maintenance in Streaming Graphs	2026	VLDB	4.1945683e-05
10,670	X-Blossom: Massive Parallelization of Graph Maximum Matching	2025	VLDB	4.1945683e-05
10,673	When Speed meets Accuracy: an Efficient and Effective Graph Model for Temporal Link Prediction	2025	VLDB	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 10 of 10 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
246	Efficient Management of Transitive Relationships in Large Data and Knowledge Bases	1989	SIGMOD	0.00030949575
279	3-HOP: A High-Compression Indexing Scheme for Reachability Query	2009	SIGMOD	0.00029113513
334	Fast and Practical Indexing and Querying of Very Large Graphs	2007	SIGMOD	0.00027081079
733	GRAIL: Scalable Reachability Index for Large Graphs	2010	VLDB	0.00017460741
788	Efficiently Answering Reachability Queries on Very Large Directed Graphs	2008	SIGMOD	0.00016650034
1,777	Reachability Queries on Large Dynamic Graphs: A Total Order Approach	2014	SIGMOD	0.00010589591
1,880	TF-Label: a Topological-Folding Labeling Scheme for Reachability Querying in a Large Graph	2013	SIGMOD	0.00010226347
2,957	Computing Label-Constraint Reachability in Graph Databases	2010	SIGMOD	7.8198686e-05
3,671	Simple, Fast, and Scalable Reachability Oracle	2013	VLDB	6.8560247e-05
4,949	Horton+: A Distributed System for Processing Declarative Reachability Queries over Partitioned Graphs	2013	VLDB	5.8113132e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
4,984	Efficient Maximum k-Defective Clique Computation with Improved Time Complexity	2023	SIGMOD	5.7867286e-05
4,344	Efficient Algorithms for Densest Subgraph Discovery on Large Directed Graphs	2020	SIGMOD	6.2744553e-05
2,436	Efficient Structural Graph Clustering: An Index-Based Approach	2018	VLDB	8.8252104e-05
3,854	Index-based Optimal Algorithms for Computing Steiner Components with Maximum Connectivity	2015	SIGMOD	6.6988744e-05
10,985	Constant-time Connectivity Querying in Dynamic Graphs	2024	SIGMOD	4.1945683e-05
10,882	Towards Scalable and Practical Batch-Dynamic Connectivity	2025	VLDB	4.1945683e-05
6,207	Efficiently Computing k-Edge Connected Components via Graph Decomposition	2013	SIGMOD	5.1572428e-05
9,239	Efficient Algorithms for Pseudoarboricity Computation in Large Static and Dynamic Graphs	2024	VLDB	4.3690661e-05
10,383	Minimum Spanning Tree Maintenance in Dynamic Graphs	2025	SIGMOD	4.1945683e-05
12,041	I/O Efficient: Computing SCCs in Massive Graphs	2013	SIGMOD	4.1945683e-05