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

Efficient Parallel Algorithms for Disjoint Paths and Connectivity
Khuller, Samir (Cornell University, 199007)This thesis is concerned with the problem of designing efficient parallel algorithms for various graphtheoretic problems. Our larger goal is to identify "tools" that would be useful in designing parallel algorithms for ... 
Extending Planar Graph Algorithms to $K_{3}$,$_{3}$free Graphs
Khuller, Samir (Cornell University, 198803)For several problems, restricting attention to special classes of graphs has yielded better algorithms. In particular, restricting to planar graphs yields efficient parallel algorithms for several graph problems. In this ... 
Flow in Planar Graphs with Vertex Capacities
Khuller, Samir; Naor, Joseph (Cornell University, 199001)Maxflow in planar graphs has always been studies with the assumption that there are capacities only on the edges. Here we consider a more general version of the problem when the vertices as well as edges have capacity ... 
On Computing Graph Closures
Khuller, Samir (Cornell University, 198806)Given a graph $G$, the closure of $G$ is the graph obtained from $G$ by recursively joining pairs of nonadjacent vertices whose degree sum is at least $n$ until no such pair remains. We give an efficient algorithm to ... 
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 ... 
Optimal Enclosure Problems
Arkin, Esther; Khuller, Samir; Mitchell, Joseph S.B. (Cornell University, 199003)We consider the following "fence enclosure" problem: Given a set $S$ of $n$ points in the plane with values $v_{i} \geq 0$, we wish to enclose a subset of the points with a fence (a simple closed curve) so as to maximize ... 
Parallel Algorithms for $K_{5}$minor Free Graphs
Khuller, Samir (Cornell University, 198804)For several problems, restricting attention to special classes of graphs has yielded better algorithms. In particular, restricting to planar graphs yields efficient parallel algorithms for several graph problems. In this ... 
Parallel Algorithms for the Subgraph Homeomorphism Problem
Khuller, Samir (Cornell University, 198902)The subgraph homeomorphism problem for a fixed graph $H$ is stated as follows: given a graph $G$, determine whether $G$ has a subgraph homeomorphic to $H$, and obtain it. We study the parallel complexity of this problem ... 
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 ...