דלג לתוכן (מקש קיצור 's')
אירועים

אירועים והרצאות בפקולטה למדעי המחשב ע"ש הנרי ומרילין טאוב

event speaker icon
דביר דוכן (הרצאה סמינריונית למגיסטר)
event date icon
יום ראשון, 28.04.2019, 11:00
event location icon
טאוב 601
event speaker icon
מנחה: 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.