Support Research supported by Deutsche Forschungsgemeinschaft, grant BO 2755/1-1.
Since some modern applications require huge graphs, explicit representations by adjacency matrices or adjacency lists may cause conflicts with memory limitations and even polynomial time algorithms are sometimes not fast enough. As time and space resources do not suffice to consider individual vertices or edges, one way out could be to deal with sets of vertices and edges represented by their characteristic functions. OBDDs are a well-known data structure for Boolean functions, therefore, a research branch has emerged which is concerned with the theoretical design and analysis of implicit algorithms for classical problems on OBDD-represented graph instances. Here, implicit algorithms have to solve problems on a given graph instance by efficient functional operations offered by the OBDD data structure.
Since OBDDs are able to take advantage over the presence of regular substructures, sublinear graph representations are possible in the implicit setting but problems typically get harder when inputs are implicitly represented. Nevertheless, OBDD-based algorithms are successful in many applications and worst-case hardness results do not adequately capture the complexity of the problems on real-world instances. Therefore, one aim is to realize for classical graph problems which cases are really difficult to process and why on the other hand the performance of OBDD-based algorithms is satisfactory in some applications. For this reason the methods to analyze implicit OBDD-based algorithms have to be strengthen. Another goal of the project is the design and the analysis of approximation algorithms in the implicit setting.