{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/72070"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/72070","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Efficient Computation of Extremal Structures in Graphs and Hypergraphs","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.","abstract_html":"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.","abstract_has_math":false,"creators":["Kelsen, Pierre"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["Ramachandran, V."],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2014,"date_issued":"2014-12-17T20:00:30Z","date_published":"2014-12-17T20:00:30Z","updated_at":"2026-07-22T22:26:06Z","subjects":["Mathematics","Computer Science"],"languages":[],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["(UMI)AAI9305575"],"render_values":[{"text":"(UMI)AAI9305575","href":null,"code":true}]}]},"links":{"outbound_url":"http://hdl.handle.net/2142/72070","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Ramachandran, V."]},{"key":"dc:creator","label":"Author","values":["Kelsen, Pierre"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2014-12-17T20:00:30Z","10000-01-01","1992"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Mathematics","Computer Science"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/72070","(UMI)AAI9305575"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["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.","Made available in DSpace on 2014-12-17T20:00:30Z (GMT). No. of bitstreams: 1 9305575.pdf: 8076112 bytes, checksum: f0d19393e6da9bb7cfa6131dbbecf25d (MD5) Previous issue date: 1992","Embargo set by: Seth Robbins for item 72238 Lift date: Forever Reason: Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs","Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs","U of I Only","186 p.","Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1992."]},{"key":"dc:title","label":"Title","values":["Efficient Computation of Extremal Structures in Graphs and Hypergraphs"]}]}],"canonical_facts":{"dc:contributor":["Ramachandran, V."],"dc:creator":["Kelsen, Pierre"],"dc:date":["2014-12-17T20:00:30Z","10000-01-01","1992"],"dc:description":["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.","Made available in DSpace on 2014-12-17T20:00:30Z (GMT). No. of bitstreams: 1 9305575.pdf: 8076112 bytes, checksum: f0d19393e6da9bb7cfa6131dbbecf25d (MD5) Previous issue date: 1992","Embargo set by: Seth Robbins for item 72238 Lift date: Forever Reason: Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs","Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs","U of I Only","186 p.","Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1992."],"dc:identifier":["http://hdl.handle.net/2142/72070","(UMI)AAI9305575"],"dc:subject":["Mathematics","Computer Science"],"dc:title":["Efficient Computation of Extremal Structures in Graphs and Hypergraphs"],"dc:type":["text"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:26:06Z"}