Hasso-Plattner-Institut
Prof. Dr. Tobias Friedrich
  
 

Research Seminar (Winter Term 2018)

<previous seminar | next seminar>

Description

A series of talks on current research and interesting topics in algorithm engineering and theoretical computer science. Everyone is welcome to attend talks. 

If you want to give a talk about a topic in algorithm engineering or theoretical computer science, please write an e-mail to Prof. Tobias Friedrich or to Ralf Rothenberger.

Announcements

For announcements of talks, subscribe to our mailing list.

Talks (click on title to show abstract)

Date Room Speaker Title
11.10. 11:00 H-E.52 Martin Schirneck

A reoccurring task in the design and profiling of relational data is the discovery of hidden dependencies between attributes. Enumerating those dependencies is equivalent to the transversal hypergraph problem. We devise a backtracking algorithm for the enumeration of inclusion-wise minimal hitting sets. It achieves polynomial delay on hypergraphs for which the size of the largest minimal transversal is bounded. The algorithm solves the extension problem for minimal hitting sets as a subroutine. Although this problem is NP-complete and W[3]-complete in general, we show that a careful implementation of the extension oracle can help avoiding the worst case on hypergraphs arising in the profiling of real-world databases, leading to significant speed-ups in practice.

This is joint work with Thomas Bläsius, Tobias Friedrich, Julius Lischeid, and Kitty Meeks.

14.11. 16:00 H-E.52 Patrick Schäfer

TBA