Efficient Computation of Extremal Structures in Graphs and Hypergraphs
Kelsen, Pierre
This item is only available for download by members of the University of Illinois community. Students, faculty, and staff at the U of I may log in with your NetID and password to view the item. If you are trying to access an Illinois-restricted dissertation or thesis, you can request a copy through your library's Inter-Library Loan office or purchase a copy directly from ProQuest.
Permalink
https://hdl.handle.net/2142/72070
Description
Title
Efficient Computation of Extremal Structures in Graphs and Hypergraphs
Author(s)
Kelsen, Pierre
Issue Date
1992
Doctoral Committee Chair(s)
Ramachandran, V.
Department of Study
Computer Science
Discipline
Computer Science
Degree Granting Institution
University of Illinois at Urbana-Champaign
Degree Name
Ph.D.
Degree Level
Dissertation
Keyword(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 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.
Use this login method if you
don't
have an
@illinois.edu
email address.
(Oops, I do have one)
IDEALS migrated to a new platform on June 23, 2022. If you created
your account prior to this date, you will have to reset your password
using the forgot-password link below.
