Hauptinhalt

Publications 2008-2012

Journal articles

• Beate Bollig (2011),
  On symbolic OBDD-based algorithms for the minimum spanning tree problem,
  accepted for Theoretical Computer Science.

• Beate Bollig (2011),
  On the OBDD complexity of the most significant bit of integer multiplication,
  Theoretical Computer Science 412(18), 1686-1695.

• Beate Bollig (2011),
  Larger lower bounds on the OBDD complexity of integer multiplication,
  Information and Computation 209, 333-343.

• Beate Bollig and Marc Gille (2011),
  Randomized OBDDs for the most significant bit of multiplication need exponential size,
  Information Processing Letters 111, 151-155.

• Beate Bollig and Jochen Klump (2011),
  New results on the most significant bit of integer multiplication,
  Theory of Computing Systems 48 (1), 170-188.

• Beate Bollig (2010),
  Exponential space complexity for OBDD-based reachability analysis,
  Information Processing Letters 110, 924-927.

• Beate Bollig, Niko Range, and Ingo Wegener (2010),
  Exact OBDD bounds for some fundamental functions,
  Theory of Computing Systems 47(2), 593-609.

• Beate Bollig (2009),
  On the size of (generalized) OBDDs for threshold functions,
  Information Processing Letters 109, 499-503.

• Beate Bollig (2008),
  A note on the size of OBDDs for the graph of integer multiplication,
  Information Processing Letters 109, 41-43.

• Beate Bollig (2008),
  The optimal read-once branching program complexity for the direct storage access function,
  Information Processing Letters 106, 171-174.

Book chapter

• Beate Bollig, Martin Sauerhoff, Detlef Sieling, and Ingo Wegener (2010),
  Binary Decision Diagrams,
  Chapter 10 in: Boolean Models and Methods in Mathematics, Computer Science, and Engineering,
  Y. Crama and P. Hammer (Ed.).

Articles in refereed conference proceedings

• Beate Bollig, Marc Gille, and Tobias Pröger (2012),
  Implicit Computation of Maximum Bipartite Matchings by Sublinear Functional Operations,
  Proc. of TAMC 2012, LNCS 7287, 473-486.

• Beate Bollig and Tobias Pröger (2012),
  An efficient implicit OBDD-based algorithm for maximal matchings,
  Proc. of LATA 2012, LNCS 7183, 143-154.

• Beate Bollig and Marc Gille (2011),
  Randomized OBDDs for the most significant bit of multiplication need exponential size,
  Proc. of SOFSEM 2011, LNCS 6543, 135-145.

• Beate Bollig (2010),
  A larger lower bound on the OBDD complexity of the most significant bit of multiplication,
  Proc. of LATIN 2010, LNCS 6034, 255-266.

• Beate Bollig (2010),
  Exponential space complexity for symbolic maximum flow algorithms in 0-1 networks,
  Proc. of MFCS 2010, LNCS 6281, 186-197.

• Beate Bollig (2010),
  On symbolic OBDD-based algorithms for the minimum spanning tree problem,
  Proc. of COCOA 2010, LNCS 6509, 16-30.

• Beate Bollig (2010),
  On symbolic representations of maximum matchings and (un)directed graphs,
  Proc. of TCS 2010, IFIP AICT 323, 263-300.

• Beate Bollig (2010),
  Symbolic OBDD-based reachability analysis needs exponential space,
  Proc. of SOFSEM 2010, LNCS 5901, 224-234.

• Beate Bollig (2009),
  Larger lower bounds on the OBDD complexity of integer multiplication,
  Proc. of LATA 2009, LNCS 5457, 212-223.

• Beate Bollig (2009),
  On the OBDD complexity of threshold functions and the variable ordering problem,
  Proc. of SOFSEM 2009, LNCS 5404, 129-140.

• Beate Bollig (2008),
  On the OBDD complexity of the most significant bit of integer multiplication,
  Proc. of TAMC 2008, LNCS 4978, 306-317.

• Beate Bollig and Jochen Klump (2008),
  New results on the most significant bit of integer multiplication,
  Proc. of ISAAC 2008, LNCS 5369, 883-894.

• Beate Bollig, Niko Range, and Ingo Wegener (2008),
  Exact OBDD Bounds for some fundamental functions,
  Proc. of SOFSEM 2008, LNCS 4910, 174-185.

Other contributions

• Beate Bollig (2009),
  Integer multiplication and the complexity of binary decision diagrams,
  EATCS Bulletin 98, June 09, 78-106.

Homepage of Beate Bollig