Approximating Probabilistic Group Steiner Trees in Graphs

Summary: Probabilistic group Steiner tree: min-weight tree whose vertices cover each PoI with joint probability ≥ threshold (NP-hard). Three approximation algorithms: Algs 1–2 give tight |Γ|- and ξ-approx (exponential in ξ or |Γ|), Alg3 is polynomial-time with looser guarantee; outperforms prior work. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 13177
Venue: VLDB
Year: 2023
Pagerank: 4.1905499e-05
Overall Rank: 11,266 | 21.71%
DOI: 10.14778/3565816.3565834

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,079	Fast Optimal Group Steiner Tree Search using GPUs	2026	SIGMOD	4.1905499e-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
260	Fast Exact Shortest-Path Distance Queries on Large Networks by Pruned Landmark Labeling	2013	SIGMOD	0.00030020929
1,653	An Experimental Study on Hub Labeling based Shortest Path Algorithms	2018	VLDB	0.0001098717
2,127	EASE: An Effective 3-in-1 Keyword Search Method for Unstructured, Semi-structured and Structured Data	2008	SIGMOD	9.4806381e-05
2,643	Scaling Distance Labeling on Small-World Networks	2019	SIGMOD	8.3894193e-05
3,873	Efficient Subgraph Similarity Search on Large Probabilistic Graph Databases	2012	VLDB	6.673504e-05
5,035	Scaling Up Distance Labeling on Graphs with Core-Periphery Properties	2020	SIGMOD	5.7414979e-05
5,697	Efficient and Progressive Group Steiner Tree Search	2016	SIGMOD	5.3672389e-05
6,574	Supporting Keyword Search in Product Database: A Probabilistic Approach	2013	VLDB	4.999847e-05
8,762	Efficient Query Answering in Probabilistic RDF Graphs	2011	SIGMOD	4.4520434e-05
11,497	Finding Group Steiner Trees in Graphs with both Vertex and Edge Weights	2021	VLDB	4.1905499e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
3,622	Efficient and Effective Algorithms for Clustering Uncertain Graphs	2019	VLDB	6.9021704e-05
7,500	Ranked Enumeration of Minimal Triangulations	2019	PODS	4.7135369e-05
10,364	Optimal Bounds for Private Minimum Spanning Trees via Input Perturbation	2025	PODS	4.1905499e-05
5,041	The Complexity of Mining Maximal Frequent Subgraphs	2013	PODS	5.7356447e-05
5,376	Minimum Spanning Trees in Temporal Graphs	2015	SIGMOD	5.5407342e-05
11,635	Hunting Multiple Bumps in Graphs	2020	VLDB	4.1905499e-05
9,246	Efficient Algorithms for Pseudoarboricity Computation in Large Static and Dynamic Graphs	2024	VLDB	4.3648789e-05
6,522	Clustering Uncertain Graphs	2018	VLDB	5.0230003e-05
5,697	Efficient and Progressive Group Steiner Tree Search	2016	SIGMOD	5.3672389e-05
11,497	Finding Group Steiner Trees in Graphs with both Vertex and Edge Weights	2021	VLDB	4.1905499e-05