Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People
Events

The Taub Faculty of Computer Science Events and Talks

Effective Enumeration of Tree Decompositions for Solver Optimization
event speaker icon
Dvir Dukhan (M.Sc. Thesis Seminar)
event date icon
Sunday, 28.04.2019, 11:00
event location icon
Taub 601
event speaker icon
Advisor: Prof. Benny Kimelfeld
Many intractable computational problems on graphs admit tractable algorithms when applied to trees or forests. In such cases, a tree decomposition of the input graph often facilitates an effective solution. Therefore, tree decompositions are critical for graph problems in the fields of databases, game theory, statistical analysis, bioinformatics and more. The goal of this research is to build an efficient tool for enumerating (producing) a large space of tree decompositions for solvers of graph problems to select from. While the research is practical, it is relying on a recent theoretical development on the complexity of this problem. We have conducted the research in three main steps: First, we have investigated and improved an existing algorithm in order to enhance its runtime performance of a single-thread execution. Then, we have developed parallelized versions of the algorithm, while retaining its formal guarantees. Lastly, we tested the usability of the algorithm in a recent framework that learns the effectiveness of a tree decomposition on different graph problems.