Pierre Kelsen

SODA Conference 1992 Conference Paper

Computing Minimal Spanning Subgraphs in Linear Time

• Xiaofeng Han
• Pierre Kelsen
• Vijaya Ramachandran
• Robert Endre Tarjan

STOC Conference 1992 Conference Paper

On the Parallel Complexity of Computing a Maximal Independent Set in a Hypergraph

• Pierre Kelsen

A maximal independent set in a hypergraph is a subset of vertices that is maximal with respect to the property of not containing any edge of the hypergraph. We show that an algorithm proposed by Beame and Luby is in randomized NC for hypergraphs in which the maximum edge size is bounded by a constant. To prove this, we bound the upper tail of sums of dependent random variables defined on the edges of a hypergraph. These bounds may be viewed as extensions of bounds on the tail of the binomial distribution. We derandomize this algorithm to obtain the first sublinear time deterministic algorithm for hypergraphs with edges of size O(1). The algorithm exhibits the following time-processor tradeoff: it can be made to run in time O( n ε ) with n O(1/ε) processors for a hypergraph on n vertices, for any ε ≥ 2 d+1 • (log log n )/(log n ); here d = O(1) denotes the maximum size of an edge in H. In particular, for any constant ε > O, we have an algorithm running in time O( n ε ) on a polynomial number of processors, and we have an algorithm running in time (log n ) O(1) on n O(log n /log log n ) processors.

SODA Conference 1991 Conference Paper

On Finding Minimal 2-Connected Subgraphs

• Pierre Kelsen
• Vijaya Ramachandran