Beate Bollig

ORCID

Publication Activity (10 Years)

Years Active: 1994-2021
Publications (10 Years): 7

Top Venues

Technical University of Dortmund, Germany (PHD)

Education History

Technical University of Dortmund, Germany

PHD

Publications

Beate Bollig, Martin Farenholtz
On the Relation Between Structured d-DNNFs and SDDs. Theory Comput. Syst. 65 (2) (2021)
Beate Bollig, Matthias Buttkus
On Limitations of Structured (Deterministic) DNNFs. Theory Comput. Syst. 64 (5) (2020)
Beate Bollig, Matthias Buttkus
On the Relative Succinctness of Sentential Decision Diagrams. Theory Comput. Syst. 63 (6) (2019)
Beate Bollig, Martin Farenholtz
On the relation between structured d-DNNFs and SDDs. CoRR (2019)
Beate Bollig, Matthias Buttkus
On the Relative Succinctness of Sentential Decision Diagrams. CoRR (2018)
Beate Bollig, Marc Bury
On the OBDD representation of some graph classes. Discret. Appl. Math. 214 (2016)
Beate Bollig
On the Minimization of (Complete) Ordered Binary Decision Diagrams. Theory Comput. Syst. 59 (3) (2016)
Beate Bollig
A simpler counterexample to a long-standing conjecture on the complexity of Bryant's apply algorithm. Inf. Process. Lett. 114 (3) (2014)
Beate Bollig, Marc Gillé, Tobias Pröger
Implicit computation of maximum bipartite matchings by sublinear functional operations. Theor. Comput. Sci. 560 (2014)
Beate Bollig, Tobias Pröger
On efficient implicit OBDD-based algorithms for maximal matchings. Inf. Comput. 239 (2014)
Beate Bollig
On the Minimization of (Complete) Ordered Binary Decision Diagrams. Electron. Colloquium Comput. Complex. 21 (2014)
Beate Bollig
On the Complexity of Some Ordering Problems. MFCS (2) (2014)
Beate Bollig
On the Width of Ordered Binary Decision Diagrams. COCOA (2014)
Beate Bollig, Michael Capelle
Priority functions for the approximation of the metric TSP. Inf. Process. Lett. 113 (14-16) (2013)
Beate Bollig
On symbolic OBDD-based algorithms for the minimum spanning tree problem. Theor. Comput. Sci. 447 (2012)
Beate Bollig, Tobias Pröger
An Efficient Implicit OBDD-Based Algorithm for Maximal Matchings. LATA (2012)
Beate Bollig, Marc Gillé, Tobias Pröger
Implicit Computation of Maximum Bipartite Matchings by Sublinear Functional Operations. TAMC (2012)
Beate Bollig
On the OBDD complexity of the most significant bit of integer multiplication. Theor. Comput. Sci. 412 (18) (2011)
Beate Bollig, Marc Gillé
Randomized OBDDs for the most significant bit of multiplication need exponential space. Inf. Process. Lett. 111 (4) (2011)
Beate Bollig, Marc Gillé
Randomized OBDDs for the Most Significant Bit of Multiplication Need Exponential Size. SOFSEM (2011)
Beate Bollig
Larger lower bounds on the OBDD complexity of integer multiplication. Inf. Comput. 209 (3) (2011)
Beate Bollig, Jochen Klump
New Results on the Most Significant Bit of Integer Multiplication. Theory Comput. Syst. 48 (1) (2011)
Beate Bollig
Exponential Space Complexity for Symbolic Maximum Flow Algorithms in 0-1 Networks. MFCS (2010)
Beate Bollig
Symbolic OBDD-Based Reachability Analysis Needs Exponential Space. SOFSEM (2010)
Beate Bollig
A Larger Lower Bound on the OBDD Complexity of the Most Significant Bit of Multiplication. LATIN (2010)
Beate Bollig
On Symbolic OBDD-Based Algorithms for the Minimum Spanning Tree Problem. COCOA (2) (2010)
Beate Bollig
Exponential space complexity for OBDD-based reachability analysis. Inf. Process. Lett. 110 (21) (2010)
Beate Bollig
On Symbolic Representations of Maximum Matchings and (Un)directed Graphs. IFIP TCS (2010)
Beate Bollig, Niko Range, Ingo Wegener
Exact OBDD Bounds for Some Fundamental Functions. Theory Comput. Syst. 47 (2) (2010)
Beate Bollig
Larger Lower Bounds on the OBDD Complexity of Integer Multiplication. LATA (2009)
Beate Bollig
On the size of (generalized) OBDDs for threshold functions. Inf. Process. Lett. 109 (10) (2009)
Beate Bollig
Integer Multiplicaton and the Complexity of Binary Decision Diagrams. Bull. EATCS 98 (2009)
Beate Bollig
On the OBDD Complexity of Threshold Functions and the Variable Ordering Problem. SOFSEM (2009)
Beate Bollig, Jochen Klump
New Results on the Most Significant Bit of Integer Multiplication. ISAAC (2008)
Beate Bollig, Niko Range, Ingo Wegener
Exact OBDD Bounds for Some Fundamental Functions. SOFSEM (2008)
Beate Bollig
A note on the size of OBDDs for the graph of integer multiplication. Inf. Process. Lett. 109 (1) (2008)
Beate Bollig
On the OBDD Complexity of the Most Significant Bit of Integer Multiplication. TAMC (2008)
Beate Bollig
The optimal read-once branching program complexity for the direct storage access function. Inf. Process. Lett. 106 (4) (2008)
Beate Bollig
On the OBDD complexity of the most significant bit of integer multiplication. Electron. Colloquium Comput. Complex. 15 (056) (2008)
Beate Bollig
The Optimal Read-Once Branching Program Complexity for the Direct Storage Access Function. Electron. Colloquium Comput. Complex. 14 (110) (2007)
Beate Bollig, Niko Range, Ingo Wegener
Exact OBDD Bounds for some Fundamental Functions. Electron. Colloquium Comput. Complex. 14 (049) (2007)
Beate Bollig
Testing Membership in Formal Languages Implicitly Represented by Boolean Functions. J. Univers. Comput. Sci. 12 (6) (2006)
Beate Bollig, Stephan Waack, Philipp Woelfel
Parity graph-driven read-once branching programs and an exponential lower bound for integer multiplication. Theor. Comput. Sci. 362 (1-3) (2006)
Beate Bollig
Property Testing and the Branching Program Size of Boolean Functions. FCT (2005)
Beate Bollig, Philipp Woelfel
A Lower Bound Technique for Nondeterministic Graph-Driven Read-Once-Branching Programs and Its Applications. Theory Comput. Syst. 38 (6) (2005)
Beate Bollig
A large lower bound on the query complexity of a simple boolean function. Inf. Process. Lett. 95 (4) (2005)
Beate Bollig
A very simple function that requires exponential size nondeterministic graph-driven read-once branching programs. Inf. Process. Lett. 86 (3) (2003)
Beate Bollig
Complexity Theoretical Results on Nondeterministic Graph-Driven Read-Once Branching Programs. STACS (2003)
Beate Bollig, Ingo Wegener
Functions that have read-once branching programs of quadratic size are not necessarily testable. Inf. Process. Lett. 87 (1) (2003)
Beate Bollig
Complexity Theoretical Results on Nondeterministic Graph-driven Read-Once Branching Programs. RAIRO Theor. Informatics Appl. 37 (1) (2003)
Beate Bollig, Philipp Woelfel
A Lower Bound Technique for Nondeterministic Graph-Driven Read-Once-Branching Programs and Its Applications. MFCS (2002)
Beate Bollig
A very simple function that requires exponential size nondeterministic graph-driven read-once branching programs Electron. Colloquium Comput. Complex. (033) (2002)
Beate Bollig, Stephan Waack, Philipp Woelfel
Parity Graph-driven Read-Once Branching Programs and an Exponential Lower Bound for Integer Multiplication. IFIP TCS (2002)
Beate Bollig, Martin Sauerhoff, Ingo Wegener
On the Nonapproximability of Boolean Functions by OBDDs and Read-k-Times Branching Programs. Inf. Comput. 178 (1) (2002)
Beate Bollig, Philipp Woelfel, Stephan Waack
Parity Graph-driven Read-Once Branching Programs and an Exponential Lower Bound for Integer Multiplication Electron. Colloquium Comput. Complex. 8 (073) (2001)
Beate Bollig, Philipp Woelfel
) for integer multiplication using universal. STOC (2001)
Beate Bollig, Martin Sauerhoff, Ingo Wegener
On the Non-Approximability of Boolean Functions by OBDDs and Read-K-Times Branching Programs. Computational Complexity Conference (2001)
Beate Bollig
Restricted Nondeterministic Read-Once Branching Programs and an Exponential Lower Bound for Integer Multiplication. RAIRO Theor. Informatics Appl. 35 (2) (2001)
Beate Bollig, Ingo Wegener
Asymptotically Optimal Bounds for OBDDs and the Solution of Some Basic OBDD Problems. J. Comput. Syst. Sci. 61 (3) (2000)
Beate Bollig
Restricted Nondeterministic Read-Once Branching Programs and an Exponential Lower Bound for Integer Multiplication. MFCS (2000)
Beate Bollig, Ingo Wegener
Approximability and Nonapproximability by Binary Decision Diagrams Electron. Colloquium Comput. Complex. 7 (52) (2000)
Beate Bollig
Restricted Nondeterministic Read-Once Branching Programs and an Exponential Lower Bound for Integer Multiplication Electron. Colloquium Comput. Complex. 7 (48) (2000)
Beate Bollig, Ingo Wegener
Asymptotically Optimal Bounds for OBDDs and the Solution of Some Basic OBDD Problems. ICALP (2000)
Beate Bollig, Ingo Wegener
Asymptotically Optimal Bounds for OBDDs and the Solution of Some Basic OBDD Problems Electron. Colloquium Comput. Complex. (48) (1999)
Beate Bollig, Martin Löbbing, Martin Sauerhoff, Ingo Wegener
On the complexity of the hidden weighted bit function for various BDD models. RAIRO Theor. Informatics Appl. 33 (2) (1999)
Beate Bollig, Ingo Wegener
Complexity Theoretical Results on Partitioned (Nondeterministic) Binary Decision Diagrams. Theory Comput. Syst. 32 (4) (1999)
Beate Bollig, Ingo Wegener
A Very Simple Function that Requires Exponential Size Read-Once Branching Programs. Inf. Process. Lett. 66 (2) (1998)
Beate Bollig, Ingo Wegener
Completeness and Non-Completeness Results with Respect to Read-Once Projections. Inf. Comput. 143 (1) (1998)
Beate Bollig, Martin Sauerhoff, Detlef Sieling, Ingo Wegener
IBDDs. Theor. Comput. Sci. 205 (1-2) (1998)
Beate Bollig, Ingo Wegener
Complexity Theoretical Results on Partitioned (Nondeterministic) Binary Decision Diagrams. MFCS (1997)
Beate Bollig, Ingo Wegener
Improving the Variable Ordering of OBDDs Is NP-Complete. IEEE Trans. Computers 45 (9) (1996)
Beate Bollig, Martin Löbbing, Ingo Wegener
On the Effect of Local Changes in the Variable Ordering of Ordered Decision Diagrams. Inf. Process. Lett. 59 (5) (1996)
Beate Bollig, Ingo Wegener
Read-once Projections and Formal Circuit Verification with Binary Decision Diagrams. STACS (1996)
Beate Bollig, Martin Hühne, Stefan Pölt, Petr Savický
On the Average Case Circuit Delay of Disjunction. Parallel Process. Lett. 5 (1995)
Beate Bollig, Ingo Wegener
Read-once Projections and Formal Circuit Verification with Binary Decision Diagrams Electron. Colloquium Comput. Complex. 2 (42) (1995)
Beate Bollig, Martin Sauerhoff, Detlef Sieling, Ingo Wegener
On the Power of Different Types of Restricted Branching Programs Electron. Colloquium Comput. Complex. 1 (26) (1994)

Beate Bollig.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Beate Bollig