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: 12335
Venue: VLDB
Year: 2021
Pagerank: 4.3925641e-05
Overall Rank: 9,096 | 36.79%
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,737	Efficient Approximation Algorithms for Minimum Cost Seed Selection with Probabilistic Coverage Guarantee	2024	SIGMOD	4.4520434e-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.00052018478
180	Influence Maximization: Near-Optimal Time Complexity Meets Practical Efficiency	2014	SIGMOD	0.00037101192
338	Influence Maximization in Near-Linear Time: A Martingale Approach	2015	SIGMOD	0.00026987013
437	Stop-and-Stare: Optimal Sampling Algorithms for Viral Marketing in Billion-scale Networks	2016	SIGMOD	0.00023237348
648	Efficient Subgraph Matching on Billion Node Graphs	2012	VLDB	0.00018688754
881	Query Processing for Sensor Networks	2003	CIDR	0.00015634948
1,652	Debunking the Myths of Influence Maximization: An In-Depth Benchmarking Study	2017	SIGMOD	0.00010999442
1,798	Online Processing Algorithms for Influence Maximization	2018	SIGMOD	0.00010500792
2,226	Holistic Influence Maximization: Combining Scalability and Efficiency with Opinion-Aware Models	2016	SIGMOD	9.2532857e-05
2,668	Influence Maximization Revisited: Efficient Reverse Reachable Set Generation with Bound Tightened	2020	SIGMOD	8.3432296e-05
4,542	Distributed Processing of k Shortest Path Queries over Dynamic Road Networks	2020	SIGMOD	6.0960736e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
7,714	Minimum Strongly Connected Subgraph Collection in Dynamic Graphs	2024	VLDB	4.6651585e-05
10,962	Efficient Maximal Biplex Enumerations with Improved Worst-Case Time Guarantee	2024	SIGMOD	4.1905499e-05
8,907	Coloring in Graph Streams via Deterministic and Adversarially Robust Algorithms	2023	PODS	4.4229886e-05
6,530	Hereditary Cohesive Subgraphs Enumeration on Bipartite Graphs: The Power of Pivot-based Approaches	2023	SIGMOD	5.0197442e-05
5,021	Maximal Defective Clique Enumeration	2023	SIGMOD	5.7481039e-05
11,063	Efficient Maximal Frequent Group Enumeration in Temporal Bipartite Graphs	2024	VLDB	4.1905499e-05
11,308	Quasi-stable Coloring for Graph Compression: Approximating Max-Flow, Linear Programs, and Centrality	2023	VLDB	4.1905499e-05
6,811	Theoretically and Practically Efficient Maximum Defective Clique Search	2024	SIGMOD	4.9139947e-05
5,764	Effective and Efficient Dynamic Graph Coloring	2018	VLDB	5.3358197e-05
3,496	Efficient Maximal Biclique Enumeration for Large Sparse Bipartite Graphs	2022	VLDB	7.0376611e-05