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: 12334
Venue: VLDB
Year: 2021
Pagerank: 4.3967784e-05
Overall Rank: 9,099 | 36.71%
DOI: 10.14778/3461535.3461536

Incoming Non-self Citations Over Time

Authors

1. Jianwen Zhao
2. Yufei Tao

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
8,741	Efficient Approximation Algorithms for Minimum Cost Seed Selection with Probabilistic Coverage Guarantee	2024	SIGMOD	4.456315e-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
90	A Data-Based Approach to Social Influence Maximization	2012	VLDB	0.00052068982
180	Influence Maximization: Near-Optimal Time Complexity Meets Practical Efficiency	2014	SIGMOD	0.00037135181
337	Influence Maximization in Near-Linear Time: A Martingale Approach	2015	SIGMOD	0.00027011645
436	Stop-and-Stare: Optimal Sampling Algorithms for Viral Marketing in Billion-scale Networks	2016	SIGMOD	0.00023259324
651	Efficient Subgraph Matching on Billion Node Graphs	2012	VLDB	0.00018648572
885	Query Processing for Sensor Networks	2003	CIDR	0.00015646925
1,652	Debunking the Myths of Influence Maximization: An In-Depth Benchmarking Study	2017	SIGMOD	0.00011010086
1,801	Online Processing Algorithms for Influence Maximization	2018	SIGMOD	0.00010510943
2,220	Holistic Influence Maximization: Combining Scalability and Efficiency with Opinion-Aware Models	2016	SIGMOD	9.2622402e-05
2,664	Influence Maximization Revisited: Efficient Reverse Reachable Set Generation with Bound Tightened	2020	SIGMOD	8.3512717e-05
4,542	Distributed Processing of k Shortest Path Queries over Dynamic Road Networks	2020	SIGMOD	6.1019408e-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
10,959	Efficient Maximal Biplex Enumerations with Improved Worst-Case Time Guarantee	2024	SIGMOD	4.1945683e-05
8,905	Coloring in Graph Streams via Deterministic and Adversarially Robust Algorithms	2023	PODS	4.427232e-05
6,532	Hereditary Cohesive Subgraphs Enumeration on Bipartite Graphs: The Power of Pivot-based Approaches	2023	SIGMOD	5.0245678e-05
11,060	Efficient Maximal Frequent Group Enumeration in Temporal Bipartite Graphs	2024	VLDB	4.1945683e-05
5,022	Maximal Defective Clique Enumeration	2023	SIGMOD	5.7536318e-05
11,306	Quasi-stable Coloring for Graph Compression: Approximating Max-Flow, Linear Programs, and Centrality	2023	VLDB	4.1945683e-05
6,813	Theoretically and Practically Efficient Maximum Defective Clique Search	2024	SIGMOD	4.9187137e-05
5,751	Effective and Efficient Dynamic Graph Coloring	2018	VLDB	5.3409543e-05
3,492	Efficient Maximal Biclique Enumeration for Large Sparse Bipartite Graphs	2022	VLDB	7.044442e-05