Author name cluster
Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.
FOCS Conference 1991 Conference Paper
Computing the connected components of an undirected graph G=(V, E) on mod V mod =n vertices and mod E mod =m edges is addressed. An efficient and simple algorithm that runs in O(lg/sup 3/2/ n) time using n+m CREW processors is presented. >
FOCS Conference 1983 Conference Paper
We give a new characterization of the planar separator theorem in terms of mutually non-containing closed Jordan Curves. using this, we develop an O(n √n logn) maximum flow algorithm for directed planar networks (hence for any planar network).
FOCS Conference 1982 Conference Paper
Algorithms are given that compute maximum flows in planar directed networks either in O((logn)3) parallel time using O(n4) processors or O((logn)2) parallel time using O(n6) processors. The resource consumption of these algorithms is dominated by the cost of finding the value of a maximum flow. When such a value is given, or when the computation is on an undirected network, the bound is O((logn)2) time using O(n4) processors. No efficient parallel algorithm is known for the maximum flow problem in general networks.
STOC Conference 1980 Conference Paper
Selection in a set requires time linear in the size of the set when there are no a priori constraints on the total orders possible for the set. Constraints often come for free, however, with sets which arise in applications. Linear time selection [B l ] can be suboptimal for such problems. We therefore generalize the well known selection problem to admit constraints on the input sets, with a view toward settling the complexity issues which arise. The generalization also applies to the other quantile problems of ranking a given element in the input set and verification of the claim that a given element has a specified rank.