JavaScript is disabled for your browser. Some features of this site may not work without it.
Browsing by Author "Vazirani, Vijay V."
Now showing items 110 of 10

Efficient Sequential and Parallel Algorithms for Maximal Bipartite Sets
Pearson, David; Vazirani, Vijay V. (Cornell University, 199108)A maximal bipartite set (MBS) in an undirected graph $G = (V, E)$ is a maximal collection of vertices $B \subseteq$ V$ whose induced subgraph is bipartite. In this paper we present efficient sequential (linear time) and ... 
NC Algorithms for Comparability Graphs, Interval Graphs, and Unique Perfect Matchings
Kozen, Dexter; Vazirani, Umesh V.; Vazirani, Vijay V. (Cornell University, 198612)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 ... 
NC Algorithms for Computing the Number of Perfect Matchings in $K_{3,3}$free Graphs and Related Problems
Vazirani, Vijay V. (Cornell University, 198708)We show that the problem of computing the number of perfect matchings in $K_{3,3}$free graphs is in $NC$. This stands in striking contrast with the #Pcompleteness of counting the number of perfect matchings in arbitrary ... 
Online Algorithms for Weighted Matching and Stable Marriages
Khuller, Samir; Mitchell, Stephen G.; Vazirani, Vijay V. (Cornell University, 199007)We give an online deterministic algorithm for the bipartite weighted matching problem that achieves a competitive ratio of $O(n)$. In fact, this algorithm is almost optimal  the lower bound on the performance ratio of ... 
Pfaffian Orientations, 0/1 Permanents, and Even Cycles in Directed Graphs
Vazirani, Vijay V.; Yannakakis, Mihali (Cornell University, 198711)The following issues in computational complexity remain imprecisely understood: the striking difference in the complexities of computing the permanent and determinant of a matrix despite their similar looking formulae, ... 
Planar Graph Coloring is Not SelfReducible Assuming $P \neq NP$
Khuller, Samir; Vazirani, Vijay V. (Cornell University, 198912)No abstract is available. 
Processor Efficient Parallel Algorithms for the Two Disjoint Paths Problem, and for Finding a Kuratowski Homeomorph
Khuller, Samir; Mitchell, Stephen G.; Vazirani, Vijay V. (Cornell University, 198904)We give an $NC$ algorithm for finding vertex disjoint $s_{1}, t_{1}$ and $s_{2}, t_{2}$ paths in an undirected graph $G$. An important step in solving the general problem is solving the planar case. A new structural ... 
Random Polynomial Time is Equal to SemiRandom Polynomial Time
Vazirani, Umesh V.; Vazirani, Vijay V. (Cornell University, 198812)We prove that any onesided error random polynomial time (RP) algorithm can be simulated with a semirandom source at no more than polynomial factor loss in efficiency. i.e. RP=SRP. This contrasts with the fact that a ... 
A Theory of Alternating Paths and Blossoms for Proving Correctness of the $O(\sqrt{VE})$ General Graph Matching Algorithm
Vazirani, Vijay V. (Cornell University, 198909)No abstract is available. 
The TwoProcessor Scheduling Problem is in Random NC
Vazirani, Umesh V.; Vazirani, Vijay V. (Cornell University, 198905)An efficient parallel algorithm $(RNC^{2})$ for the twoprocessor scheduling problem is presented. An interesting feature of this algorithm is that it finds a highest level first schedule: such a schedule defines a ...