Design and analysis of implicit BDD-based graph algorithms
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
-
(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
-
(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
-
(2014). On efficient implicit OBDD-based algorithms for maximal matchings. Information and Computation 239, 29-43
Beate Bollig und Tobias Pröger
-
On the Minimization of (Complete) Ordered Binary Decision Diagrams. Theory of Computing Systems, Oct 2016, Vol 59, Issue 3, pp 532–559
Beate Bollig