Files in this item
Files  Description  Format 

application/pdf 9305575.pdf (8MB)  (no description provided) 
Description
Title:  Efficient Computation of Extremal Structures in Graphs and Hypergraphs 
Author(s):  Kelsen, Pierre 
Doctoral Committee Chair(s):  Ramachandran, V. 
Department / Program:  Computer Science 
Discipline:  Computer Science 
Degree Granting Institution:  University of Illinois at UrbanaChampaign 
Degree:  Ph.D. 
Genre:  Dissertation 
Subject(s):  Mathematics
Computer Science 
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 2edgeconnected 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. 
Issue Date:  1992 
Type:  Text 
Description:  186 p. Thesis (Ph.D.)University of Illinois at UrbanaChampaign, 1992. 
URI:  http://hdl.handle.net/2142/72070 
Other Identifier(s):  (UMI)AAI9305575 
Date Available in IDEALS:  20141217 
Date Deposited:  1992 
This item appears in the following Collection(s)

Dissertations and Theses  Computer Science
Dissertations and Theses from the Dept. of Computer Science 
Graduate Dissertations and Theses at Illinois
Graduate Theses and Dissertations at Illinois