Powered by OpenAIRE graph

Computations on Networks with a Tree-Structure: From Theory to Practice

Funder: Netherlands Organisation for Scientific Research (NWO)Project code: 040.40.008

Computations on Networks with a Tree-Structure: From Theory to Practice

Description

Dynamic programming based on tree decomposition is one of the most successful approaches for solving important hard problems on networks, with problems ranging from several application areas (including operations research, computational biology, etc.). In theory, Bodlaenders algorithm and Courcelles theorem give for a large collection of problems algorithms that solve them in time linear in the number of vertices, assuming we have a graph or network with the appropriate structure (i.e., the treewidth is bounded); a condition that appears to be true for many networks from quite various applications. However, while these results and the corresponding algorithms play a central role in many theoretical / foundational studies, and are seen as cornerstones in the field of parameterized algorithms (“fixed parameter tractability”), the direct practical use is under debate: while asymptotic optimal, the constant factors hidden in the big-Oh notation are huge. Thus, a worthy topic of study is to see how the theoretical results can be moved to useful practical results. This asks for the development of new algorithmic insights and algorithm engineering studies, alongside with further insights in the structure of networks that allow these type of dynamic programming algorithms. Both Japan and the Netherlands have strong and well known researchers in this area. This seminar brings together these experts to initiate new studies towards significant progress both in practice as in theory.

Data Management Plans
Powered by OpenAIRE graph

Do the share buttons not appear? Please make sure, any blocking addon is disabled, and then reload the page.

All Research products
arrow_drop_down
<script type="text/javascript">
<!--
document.write('<div id="oa_widget"></div>');
document.write('<script type="text/javascript" src="https://www.openaire.eu/index.php?option=com_openaire&view=widget&format=raw&projectId=nwo_________::06b7a575d08998a1033b097b13d2b244&type=result"></script>');
-->
</script>
For further information contact us at helpdesk@openaire.eu

No option selected
arrow_drop_down