Approximating Probabilistic Group Steiner Trees in Graphs

Summary: Formulates probabilistic group Steiner trees for uncertain vertex properties, requiring threshold joint coverage of every PoI at minimum edge cost. Provides three approximation algorithms trading tight |Γ|/ξ guarantees against exponential versus polynomial time, outperforming prior work empirically. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: 13364
Venue: VLDB
Year: 2023
Pagerank: 5.093636e-05
Overall Rank: 11,463 | 21.36%
DOI: 10.14778/3565816.3565834

Incoming Non-self Citations Over Time

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

Authors

1. Shuang Yang (Renmin University of China)
2. Yahui Sun (Renmin University of China)
3. Jiesong Liu (Renmin University of China)
4. Xiaokui Xiao (National University of Singapore)
5. Rong-Hua Li (Beijing Institute of Technology)
6. Zhewei Wei (Renmin University of China)

BibTeX Citation

@article{yang_vldb23,
        title = {{Approximating Probabilistic Group Steiner Trees in Graphs}},
        author = {Yang, Shuang and Sun, Yahui and Liu, Jiesong and Xiao, Xiaokui and Li, Rong-Hua and Wei, Zhewei},
        journal = {PVLDB},
        series = {{VLDB} '23},
        volume = {16},
        number = {2},
        pages = {343--355},
        doi = {10.14778/3565816.3565834},
        url = {https://doi.org/10.14778/3565816.3565834},
        year = {2023}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,370	Fast Optimal Group Steiner Tree Search using GPUs	2026	SIGMOD	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
195	Fast Exact Shortest-Path Distance Queries on Large Networks by Pruned Landmark Labeling	2013	SIGMOD	0.00025813775
1,309	An Experimental Study on Hub Labeling based Shortest Path Algorithms	2018	VLDB	0.00011210911
1,878	EASE: An Effective 3-in-1 Keyword Search Method for Unstructured, Semi-structured and Structured Data	2008	SIGMOD	9.5651166e-05
2,152	Scaling Distance Labeling on Small-World Networks	2019	SIGMOD	9.0778596e-05
3,548	Efficient Subgraph Similarity Search on Large Probabilistic Graph Databases	2012	VLDB	7.3214417e-05
4,403	Scaling Up Distance Labeling on Graphs with Core-Periphery Properties	2020	SIGMOD	6.7229209e-05
6,466	Supporting Keyword Search in Product Database: A Probabilistic Approach	2013	VLDB	5.871262e-05
6,469	Efficient and Progressive Group Steiner Tree Search	2016	SIGMOD	5.8710857e-05
8,935	Efficient Query Answering in Probabilistic RDF Graphs	2011	SIGMOD	5.3483178e-05
11,691	Finding Group Steiner Trees in Graphs with both Vertex and Edge Weights	2021	VLDB	5.093636e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,559	Efficient and Effective Algorithms for Clustering Uncertain Graphs	2019	VLDB
2	7,923	Ranked Enumeration of Minimal Triangulations	2019	PODS
3	9,538	Optimal Bounds for Private Minimum Spanning Trees via Input Perturbation	2025	PODS
4	7,522	The Complexity of Mining Maximal Frequent Subgraphs	2013	PODS
5	5,028	Minimum Spanning Trees in Temporal Graphs	2015	SIGMOD
6	11,826	Hunting Multiple Bumps in Graphs	2020	VLDB
7	9,387	Efficient Algorithms for Pseudoarboricity Computation in Large Static and Dynamic Graphs	2024	VLDB
8	6,345	Clustering Uncertain Graphs	2018	VLDB
9	6,469	Efficient and Progressive Group Steiner Tree Search	2016	SIGMOD
10	11,691	Finding Group Steiner Trees in Graphs with both Vertex and Edge Weights	2021	VLDB