Now showing items 1-4 of 4

  • Improved bounds for the max-flow min-multicut ratio for planar and Kr, r-free graphs 

    Tardos, Éva; Vazirani, Vijay V (1993)
    We consider the version of the multicommodity flow problem in which the objective is to maximize the sum of commodities routed. Garg, Vazirani and Yannakakis proved that the minimum multicut and maximum flow ratio for this ...
  • Multiway cuts in node weighted graphs 

    Garg, Naveen; Vazirani, Vijay V; Yannakakis, Mihalis (2004)
    A (2−2/k) approximation algorithm is presented for the node multiway cut problem, thus matching the result of Dahlhaus et al. (SIAM J. Comput. 23 (4) (1994) 864–894) for the edge version of this problem. This is done by ...
  • On-line algorithms for weighted bipartite matching and stable marriages 

    Khuller, Samir; Mitchell, Stephen G; Vazirani, Vijay V (1994)
    We give an on-line deterministic algorithm for the weighted bipartite matching problem that achieves a competitive ratio of (2n−1) in any metric space (where n is the number of vertices). This algorithm is optimal - there ...
  • Planar graph coloring is not self-reducible, assuming P ≠ NP 

    Vazirani, Vijay V; Khuller, Samir (1991)
    We show that obtaining the lexicographically first four coloring of a planar graph is NP-hard. This shows that planar graph four-coloring is not self-reducible, assuming P≠ NP. One consequence of our result is that the ...