Index-based Optimal Algorithms for Computing Steiner Components with Maximum Connectivity

Summary: Index-based optimal algorithms for Steiner components with maximum connectivity (SMCC) using a novel index; runtime linear in the result size. Supports size-constrained SMCC, connectivity-only metrics, batch processing, and incremental updates; experiments show speedups. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 5035
Venue: SIGMOD
Year: 2015
Pagerank: 6.6988744e-05
Overall Rank: 3,854 | 73.19%
DOI: 10.1145/2723372.2746486

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 21 of 21 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,286	Effective and Efficient Community Search over Large Heterogeneous Information Networks	2020	VLDB	9.0982591e-05
2,721	Effective and Efficient Relational Community Detection and Search in Large Dynamic Heterogeneous Information Networks	2020	VLDB	8.2345495e-05
3,369	Query Driven-Graph Neural Networks for Community Search: From Non-Attributed, Attributed, to Interactive Attributed	2022	VLDB	7.171452e-05
3,969	Efficient Size-Bounded Community Search over Large Networks	2021	VLDB	6.5787567e-05
5,513	Effective Community Search over Large Star-Schema Heterogeneous Information Networks	2022	VLDB	5.4641695e-05
5,610	Influential Community Search over Large Heterogeneous Information Networks	2023	VLDB	5.4118541e-05
5,643	An Optimal and Progressive Approach to Online Search of Top-K Influential Communities	2018	VLDB	5.3928286e-05
6,259	Neural Attributed Community Search at Billion Scale	2023	SIGMOD	5.1355079e-05
6,588	Efficient Progressive Minimum k-Core Search	2020	VLDB	5.0020648e-05
7,346	I/O Efficient ECC Graph Decomposition via Graph Reduction	2016	VLDB	4.7556749e-05
8,630	A Near-Optimal Approach to Edge Connectivity-Based Hierarchical Graph Decomposition	2022	VLDB	4.480887e-05
8,821	Efficient Unsupervised Community Search with Pre-trained Graph Transformer	2024	VLDB	4.4417735e-05
8,897	BCviz: A Linear-Space Index for Mining and Visualizing Cohesive Bipartite Subgraphs	2025	SIGMOD	4.427232e-05
8,975	Truss-based Community Search over Streaming Directed Graphs	2024	VLDB	4.4179255e-05
9,390	Efficient Maximum s-Bundle Search via Local Vertex Connectivity	2025	SIGMOD	4.3441378e-05
9,552	Cohesiveness-aware Hierarchical Compressed Index for Community Search on Attributed Graphs	2025	SIGMOD	4.3254416e-05
10,076	Efficient Size-Bounded Community Search, Revisited: Frameworks for Practical Improvements	2026	SIGMOD	4.1945683e-05
10,159	Efficient Influential Community Search over Dynamic Graphs	2026	SIGMOD	4.1945683e-05
10,240	Effective Durable Community Search in Large Temporal Graph	2026	VLDB	4.1945683e-05
10,552	Synergetic Community Search over Large Multilayer Graphs	2025	VLDB	4.1945683e-05
10,553	Searching and Detecting Structurally Similar Communities in Large Heterogeneous Information Networks	2025	VLDB	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 7 of 7 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
110	On Triangulation-based Dense Neighborhood Graph Discovery	2011	VLDB	0.00047892924
283	Querying K-Truss Community in Large and Dynamic Graphs	2014	SIGMOD	0.00029041257
353	Local Search of Communities in Large Graphs	2014	SIGMOD	0.00026277992
370	Online Search of Overlapping Communities	2013	SIGMOD	0.00025415479
686	Finding Maximal Cliques in Massive Networks by H*-graph	2010	SIGMOD	0.00018178029
3,020	GConnect: A Connectivity Index for Massive Disk-Resident Graphs	2009	VLDB	7.6992238e-05
6,207	Efficiently Computing k-Edge Connected Components via Graph Decomposition	2013	SIGMOD	5.1572428e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
7,716	Minimum Strongly Connected Subgraph Collection in Dynamic Graphs	2024	VLDB	4.6696364e-05
1,777	Reachability Queries on Large Dynamic Graphs: A Total Order Approach	2014	SIGMOD	0.00010589591
6,657	On Querying Historical Connectivity in Temporal Graphs	2024	SIGMOD	4.9720132e-05
7,346	I/O Efficient ECC Graph Decomposition via Graph Reduction	2016	VLDB	4.7556749e-05
10,985	Constant-time Connectivity Querying in Dynamic Graphs	2024	SIGMOD	4.1945683e-05
8,630	A Near-Optimal Approach to Edge Connectivity-Based Hierarchical Graph Decomposition	2022	VLDB	4.480887e-05
2,436	Efficient Structural Graph Clustering: An Index-Based Approach	2018	VLDB	8.8252104e-05
4,970	On Querying Connected Components in Large Temporal Graphs	2023	SIGMOD	5.7945079e-05
12,041	I/O Efficient: Computing SCCs in Massive Graphs	2013	SIGMOD	4.1945683e-05
6,207	Efficiently Computing k-Edge Connected Components via Graph Decomposition	2013	SIGMOD	5.1572428e-05