Minimum Strongly Connected Subgraph Collection in Dynamic Graphs

Summary: Introduces MSCSC: covering maximal mutually reachable node sets with the minimum edges, an NP-hard alternative to conventional SCCs. Provides one-pass linear-time approximations plus DAG-based insertion and localized deletion maintenance, scaling to 3-billion-edge graphs. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: 13565
Venue: VLDB
Year: 2024
Pagerank: 5.5927377e-05
Overall Rank: 7,578 | 48.01%
DOI: 10.14778/3648160.3648173

Incoming Non-self Citations Over Time

Authors

1. Xin Chen (Chinese University of Hong Kong)
2. Jieming Shi (Hong Kong Polytechnic University)
3. You Peng (University of New South Wales)
4. Wenqing Lin (Tencent)
5. Sibo Wang (Chinese University of Hong Kong)
6. Wenjie Zhang (University of New South Wales)

BibTeX Citation

@article{chen_vldb24,
        title = {{Minimum Strongly Connected Subgraph Collection in Dynamic Graphs}},
        author = {Chen, Xin and Shi, Jieming and Peng, You and Lin, Wenqing and Wang, Sibo and Zhang, Wenjie},
        journal = {PVLDB},
        series = {{VLDB} '24},
        volume = {17},
        number = {6},
        pages = {1324--1336},
        doi = {10.14778/3648160.3648173},
        url = {https://doi.org/10.14778/3648160.3648173},
        year = {2024}
}

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,609	Efficient Temporal Edge-Core Maintenance in Streaming Graphs	2026	VLDB	5.093636e-05
10,919	X-Blossom: Massive Parallelization of Graph Maximum Matching	2025	VLDB	5.093636e-05
10,922	When Speed meets Accuracy: an Efficient and Effective Graph Model for Temporal Link Prediction	2025	VLDB	5.093636e-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
269	3-HOP: A High-Compression Indexing Scheme for Reachability Query	2009	SIGMOD	0.00022786599
282	Efficient Management of Transitive Relationships in Large Data and Knowledge Bases	1989	SIGMOD	0.0002242162
322	Fast and Practical Indexing and Querying of Very Large Graphs	2007	SIGMOD	0.00021275303
679	GRAIL: Scalable Reachability Index for Large Graphs	2010	VLDB	0.00015055389
746	Efficiently Answering Reachability Queries on Very Large Directed Graphs	2008	SIGMOD	0.00014402233
1,533	TF-Label: a Topological-Folding Labeling Scheme for Reachability Querying in a Large Graph	2013	SIGMOD	0.00010467148
1,796	Reachability Queries on Large Dynamic Graphs: A Total Order Approach	2014	SIGMOD	9.7380494e-05
2,490	Computing Label-Constraint Reachability in Graph Databases	2010	SIGMOD	8.5090456e-05
3,278	Simple, Fast, and Scalable Reachability Oracle	2013	VLDB	7.5712342e-05
4,813	Horton+: A Distributed System for Processing Declarative Reachability Queries over Partitioned Graphs	2013	VLDB	6.4974292e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,737	Efficient Algorithms for Densest Subgraph Discovery on Large Directed Graphs	2020	SIGMOD
2	4,672	Efficient Maximum k-Defective Clique Computation with Improved Time Complexity	2023	SIGMOD
3	3,261	Index-based Optimal Algorithms for Computing Steiner Components with Maximum Connectivity	2015	SIGMOD
4	2,482	Efficient Structural Graph Clustering: An Index-Based Approach	2018	VLDB
5	11,198	Constant-time Connectivity Querying in Dynamic Graphs	2024	SIGMOD
6	11,105	Towards Scalable and Practical Batch-Dynamic Connectivity	2025	VLDB
7	5,540	Efficiently Computing k-Edge Connected Components via Graph Decomposition	2013	SIGMOD
8	9,387	Efficient Algorithms for Pseudoarboricity Computation in Large Static and Dynamic Graphs	2024	VLDB
9	10,671	Minimum Spanning Tree Maintenance in Dynamic Graphs	2025	SIGMOD
10	12,239	I/O Efficient: Computing SCCs in Massive Graphs	2013	SIGMOD