Approximation Algorithms

  1. H. Saran and V.V. Vazirani, Finding k-cuts within Twice the Optimal. SIAM J. of Computing 24, 1 (1995).
  2. N. Garg, V.V. Vazirani, and M. Yannakakis, Approximate Max-flow Min-(multi)cut Theorems and their Applications. SIAM J. of Computing 25, 2 (1996) 235-251.
  3. D. Williamson, M. Goemans, M. Mihail, and V.V. Vazirani, A Primal-Dual Approximation Algorithm for the Generalized Steiner Network Problem. Combinatorica, 15 (1995) 435-454.
  4. S. Rajagopalan and V.V. Vazirani, Primal-Dual RNC Approximation Algorithms for (multi)Set (multi)Cover and Covering Integer Programs. SIAM J. of Computing 28, 2 (1998) 525-540.
  5. N. Garg, H. Saran, and V.V. Vazirani, Finding Separator Cuts in Planar Graphs within Twice the Optimal. SIAM J. of Computing 29, 1 (1999) 159-179.

Coding Theory

  1. V.V. Vazirani, H. Saran, and B.S. Rajan, An Efficient Algorithm for Constructing Minimal Trellises for Codes over Finite Abelian Groups. IEEE Transactions on Information Theory, special issue on Codes and Complexity, Vol. 42, No. 6 (1996) 144-153.
  2. K. Jain, I. Mandoiu, and V.V. Vazirani, The ``Art of Trellis Decoding'' is Computationally Hard -- for Large Fields. IEEE Transactions on Information Theory, Vol. 44, No. 3 (1998) 1211-1214.

Algorithmic Matching Theory

  1. S. Micali and V.V. Vazirani, An $O(\sqrt{V}E)$ Algorithm for Finding Maximum Matching in General Graphs. Proc. 21st Annual IEEE Symposium on Foundations of Computer Science (1980) 17-27.
  2. M.O. Rabin and V.V. Vazirani, Maximum Matchings in General Graphs through Randomization. Journal of Algorithms, Vol. 10, No. 4 (1989) 557-567.
  3. K. Mulmuley, U.V. Vazirani, and V.V. Vazirani, Matching is as Easy as Matrix Inversion. Combinatorica 7:1 (1987) 105-114.
  4. V.V. Vazirani and M. Yannakakis, Pfaffian Orientations, 0/1 Permanents, and Even Cycles in Directed Graphs. Discrete and Applied Mathematics, 25. (1989) 179-190.
  5. V.V. Vazirani, A Theory of Alternating Paths and Blossoms for Proving Correctness of the $O(\sqrt{V} E)$ Maximum Matching Algorithm. Combinatorica 14:1 (1994) 71-109.
  6. H. Narayanan, H. Saran, and V.V. Vazirani, Randomized Parallel Algorithms for Matroid Union and Intersection, with Applications to Arboresences, and Edge-Disjoint Spanning Trees. SIAM J. Computing Vol. 23 No. 2 (1994) 387-397.

Complexity Theory

  1. L.G. Valiant and V.V. Vazirani, NP is as Easy as Detecting Unique Solutions. Theoretical Computer Science, 47(1986), 85-94.
  2. M.R. Jerrum, L.G. Valiant, and V.V. Vazirani, Random Generation of Combinatorial Structures from a Uniform Distribution. Theoretical Computer Science 44 (1986) 169-188.
  3. U.V. Vazirani and V.V. Vazirani, Random Polynomial Time is Equal to Semi-random Polynomial Time. Proc. 26th Annual IEEE Symposium on Foundations of Computer Science (1985), 417-428.