Design and analysis of implicit BDD-based graph algorithms

• Applicant: Professorin Dr. Beate Bollig
• Subject Area: Theoretical Computer Science
• Term: from 2010 to 2015
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 173772243

Given the rapid growth of application-based networks, the design and analysis of graph algorithms is faced with a new challenge, e.g., if it is no longer possible to store all vertices and edges of an input graph explicitly because of space requirements. Therefore, in the last years a research branch has emerged which is concerned with the design and analysis of implicit BDD-based algorithms for classical graph problems.Due to the inherent complexity even of simple graph problems, the application of implicit methods is only an heuristic approach and one aim is to explore the limits of practical applicability of BDD-based graph algorithms.Which kind of inputs needs a large amount of resources?What is the behaviour of implicit graph algorithms on typical inputs?Contributions should be provided to answer these questions and methods should be developped in order to be able to use the full potential of BDD-representations.To refine the methods for the design and the analysis of implicit algorithms,structural differences and similarities between explicit and implicit methods should be identified.Deeper insight into the benefit of implicit methods should be provided by experimental and theoretical analysis.

• DFG Programme: Research Grants