Now showing items 1-3 of 3

    • NC Algorithms for Comparability Graphs, Interval Graphs, and Unique Perfect Matchings 

      Kozen, Dexter; Vazirani, Umesh V.; Vazirani, Vijay V. (Cornell University, 1986-12)
      Laszlo Lovasz recently posed the following problem: "Is there an NC algorithm for testing if a given graph has a unique perfect matching?" We present such an algorithm for bipartite graphs. We also give NC algorithms ...
    • Random Polynomial Time is Equal to Semi-Random Polynomial Time 

      Vazirani, Umesh V.; Vazirani, Vijay V. (Cornell University, 1988-12)
      We prove that any one-sided error random polynomial time (RP) algorithm can be simulated with a semi-random source at no more than polynomial factor loss in efficiency. i.e. RP=SRP. This contrasts with the fact that a ...
    • The Two-Processor Scheduling Problem is in Random NC 

      Vazirani, Umesh V.; Vazirani, Vijay V. (Cornell University, 1989-05)
      An efficient parallel algorithm $(RNC^{2})$ for the two-processor scheduling problem is presented. An interesting feature of this algorithm is that it finds a highest level first schedule: such a schedule defines a ...