Files in this item
|(no description provided)|
|Title:||Efficient Computation of Extremal Structures in Graphs and Hypergraphs|
|Doctoral Committee Chair(s):||Ramachandran, V.|
|Department / Program:||Computer Science|
|Degree Granting Institution:||University of Illinois at Urbana-Champaign|
|Abstract:||An independence system consists of a ground set and a collection of subsets of the ground set called independent sets with the property that any subset of an independent set is independent. We study the problem of computing a maximal independent set (mis) in an independence system. We propose two approaches for designing fast parallel algorithms for special cases of this problem.
The first approach is to consider special independence systems in which the ground set is the set of edges of a graph and a subset of edges is independent if its removal from the graph leaves a graph with a given monotone property. Finding a maximal independent set in such an independence system is equivalent to finding a minimal spanning subgraph of a graph with a given property. We obtain the following results. We have efficient NC algorithms for finding a minimal 2-edge-connected and a minimal biconnected spanning subgraph. We also obtain linear time sequential algorithms for these problems. For both directed and undirected graphs we give a general algorithm for computing minimal spanning subgraphs and we develop techniques for analyzing this algorithm. Using these techniques we provide a tight analysis of an algorithm for finding a minimal strongly connected spanning subgraph.
The second approach consists in reducing the problem to that of computing a maximal independent set in a hypergraph (i.e., a set of vertices in the hypergraph that does not contain an edge of the hypergraph). We study the parallel complexity of this problem. We have an efficient NC algorithm for hypergraphs with edges of size at most 3. We show that a randomized parallel algorithm proposed by Beame and Luby is in RNC for hypergraphs in which the maximum edge size is bounded by a constant. To prove this, we develop new bounds on the upper tail of sums of random variables defined on the edges of a hypergraph. We derandomize the algorithm to obtain a sublinear time deterministic parallel algorithm running with a polynomial number of processors for hypergraphs with edges of constant size.
Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1992.
|Date Available in IDEALS:||2014-12-17|