Entwurf und Analyse impliziter BDD-basierter Graphalgorithmen

• Antragstellerin: Professorin Dr. Beate Bollig
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2010 bis 2015
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 173772243

• Erstellungsjahr: 2015

Zusammenfassung der Projektergebnisse

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.

Projektbezogene Publikationen (Auswahl)

• (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
  (Siehe online unter 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
  (Siehe online unter 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
  (Siehe online unter 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
  (Siehe online unter 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
  (Siehe online unter https://doi.org/10.1007/s00224-015-9657-x)