Parallel Hypergraph Transversals

Date and time: 
Monday, December 3, 2018 - 14:00
Location: 
220 Deschutes
Author(s):
Roscoe Casita
University of Oregon
Host/Committee: 
  • Boyana Norris (chair)
  • Andrzej Proskurowski
  • Chris Wilson

The DRP introduces parallel algorithms to compute all minimal transversals of a hypergraph. State of the art hypergraph transversal algorithms are used for design and analyzed for comparison. The critical vertex of hyperedges concept is used to conjunction with partitioning of hyperedges. Parallelism is achieved by duplicating an iterative state machine and splitting the workload. Multiple Hypergraphs are evaluated to demonstrate the various benefits and drawbacks to the algorithms.