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

• Final Report Year: 2015

Final Report Abstract

Wir haben in vielen Bereichen unseres Vorhabens deutliche Fortschritte erzielt. Während es für das NP-harte Variablenordnungsproblem jedoch zumindest Heuristiken gibt, die in den Anwendungen zufriedenstellende Ergebnisse liefern, stehen solche für das Knotencodierungsproblem noch aus. So konnten wir zwar für eingeschränkte Graphklassen wie Intervallgraphen gute Knotencodierungen angeben, die die Intervalldarstellung der Graphen ausnutzen, doch für allgemeine Graphen, wie wir sie z.B. in experimentellen Vergleichen benutzt haben, fehlen Methoden, wie man kleine OBDD-Repräsentationen erhält. Deshalb haben wir die Codierung häufig aus den entsprechenden Graphbeschreibungen übernommen. Verfahren, wie implizite Darstellungen bezüglich ihrer Größe weiter verbessert werden können, wären wünschenswert. Zwei unserer wissenschaftlichen Arbeiten sind mit einem Best Student Paper Award auf einer internationalen Konferenz ausgezeichnet worden.

Publications

• (2012). On symbolic OBDD-based algorithms for the minimum spanning tree problem. Theoretical Computer Science 447, 2-12
  Beate Bollig
  
• (2013). OBDD-based representations of interval graphs. Proc. of WG 2013, Springer, LNCS 8165, 286-297. (Ausgezeichnet mit einem Best Student Paper Award.)
  Marc Gillé
  
• (2013). Priority functions for the approximation of the metric TSP. Information Processing Letters 113, 584-591
  Beate Bollig und Michael Capelle
  (See online at https://doi.org/10.1016/j.ipl.2013.05.002)
• (2014). A simpler counterexample to a long-standing conjecture on the complexity of Bryant’s apply algorithm. Information Processing Letters 114 (3), 124–129
  Beate Bollig
  (See online at https://doi.org/10.1016/j.ipl.2013.11.003)
• (2014). Implicit computation of maximum bipartite matchings by sublinear functional operations. Theoretical Computer Science 560, 131-146
  Beate Bollig, Marc Gillé und Tobias Pröger
  (See online at https://doi.org/10.1016/j.tcs.2014.07.020)
• (2014). On efficient implicit OBDD-based algorithms for maximal matchings. Information and Computation 239, 29-43
  Beate Bollig und Tobias Pröger
  (See online at https://doi.org/10.1016/j.ic.2014.08.006)
• On the Minimization of (Complete) Ordered Binary Decision Diagrams. Theory of Computing Systems, Oct 2016, Vol 59, Issue 3, pp 532–559
  Beate Bollig
  (See online at https://doi.org/10.1007/s00224-015-9657-x)