Efficient Computation of Extremal Structures in Graphs and Hypergraphs

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.

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Computer Science

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2014

Author dc:creator

• Kelsen, Pierre

Contributors dc:contributor

• Ramachandran, V.

• Mathematics
• Computer Science

Identifier

(UMI)AAI9305575

OAI identifier oai:identifier

oai:www.ideals.illinois.edu:2142/72070