Minimum Vertex Augmentation

Summary: Minimum Vertex Augmentation (MVA) flips a subset of 0-vertices so the 1-vertex induced subgraph satisfies a user-defined pi. A generic algorithmic paradigm with strong guarantees and scalable techniques, validated by extensive experiments on real graphs. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 12522
Venue: VLDB
Year: 2021
Pagerank: 5.2993405e-05
Overall Rank: 9,244 | 36.58%
DOI: 10.14778/3461535.3461536

Incoming Non-self Citations Over Time

Authors

1. Jianwen Zhao (Chinese University of Hong Kong)
2. Yufei Tao (Chinese University of Hong Kong)

BibTeX Citation

@article{zhao_vldb21,
        title = {{Minimum Vertex Augmentation}},
        author = {Zhao, Jianwen and Tao, Yufei},
        journal = {PVLDB},
        series = {{VLDB} '21},
        volume = {14},
        number = {9},
        pages = {1454--1466},
        doi = {10.14778/3461535.3461536},
        url = {https://doi.org/10.14778/3461535.3461536},
        year = {2021}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
8,913	Efficient Approximation Algorithms for Minimum Cost Seed Selection with Probabilistic Coverage Guarantee	2024	SIGMOD	5.3483178e-05

Outgoing Citations (Sorted by Pagerank)

Showing 11 of 11 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
194	Influence Maximization: Near-Optimal Time Complexity Meets Practical Efficiency	2014	SIGMOD	0.000259047
296	A Data-Based Approach to Social Influence Maximization	2012	VLDB	0.00022220351
315	Influence Maximization in Near-Linear Time: A Martingale Approach	2015	SIGMOD	0.00021436156
442	Efficient Subgraph Matching on Billion Node Graphs	2012	VLDB	0.00018398144
453	Stop-and-Stare: Optimal Sampling Algorithms for Viral Marketing in Billion-scale Networks	2016	SIGMOD	0.00018145895
765	Query Processing for Sensor Networks	2003	CIDR	0.00014217472
1,478	Online Processing Algorithms for Influence Maximization	2018	SIGMOD	0.00010651983
1,531	Debunking the Myths of Influence Maximization: An In-Depth Benchmarking Study	2017	SIGMOD	0.00010472526
1,919	Holistic Influence Maximization: Combining Scalability and Efficiency with Opinion-Aware Models	2016	SIGMOD	9.4850778e-05
2,320	Influence Maximization Revisited: Efficient Reverse Reachable Set Generation with Bound Tightened	2020	SIGMOD	8.7576221e-05
4,685	Distributed Processing of k Shortest Path Queries over Dynamic Road Networks	2020	SIGMOD	6.5628805e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	7,578	Minimum Strongly Connected Subgraph Collection in Dynamic Graphs	2024	VLDB
2	11,173	Efficient Maximal Biplex Enumerations with Improved Worst-Case Time Guarantee	2024	SIGMOD
3	9,060	Coloring in Graph Streams via Deterministic and Adversarially Robust Algorithms	2023	PODS
4	5,374	Hereditary Cohesive Subgraphs Enumeration on Bipartite Graphs: The Power of Pivot-based Approaches	2023	SIGMOD
5	5,133	Maximal Defective Clique Enumeration	2023	SIGMOD
6	11,267	Efficient Maximal Frequent Group Enumeration in Temporal Bipartite Graphs	2024	VLDB
7	11,505	Quasi-stable Coloring for Graph Compression	2023	VLDB
8	6,268	Theoretically and Practically Efficient Maximum Defective Clique Search	2024	SIGMOD
9	5,797	Effective and Efficient Dynamic Graph Coloring	2018	VLDB
10	2,860	Efficient Maximal Biclique Enumeration for Large Sparse Bipartite Graphs	2022	VLDB