Beate Bollig

78 papers A* 2A 3B 11C 5Journal 51Unranked 4
YearRankTypeTitle / Venue / Authors
2021 J jnl
On the Relation Between Structured d-DNNFs and SDDs.
Theory Comput. Syst.
Beate Bollig, Martin Farenholtz
2020 J jnl
On Limitations of Structured (Deterministic) DNNFs.
Theory Comput. Syst.
Beate Bollig, Matthias Buttkus
2019 J jnl
On the Relative Succinctness of Sentential Decision Diagrams.
Theory Comput. Syst.
Beate Bollig, Matthias Buttkus
2019 J jnl
On the relation between structured d-DNNFs and SDDs.
CoRR
Beate Bollig, Martin Farenholtz
2018 J jnl
On the Relative Succinctness of Sentential Decision Diagrams.
CoRR
Beate Bollig, Matthias Buttkus
2016 J jnl
On the Minimization of (Complete) Ordered Binary Decision Diagrams.
Theory Comput. Syst.
Beate Bollig
2016 J jnl
On the OBDD representation of some graph classes.
Discret. Appl. Math.
Beate Bollig, Marc Bury
2014 J jnl
A simpler counterexample to a long-standing conjecture on the complexity of Bryant's apply algorithm.
Inf. Process. Lett.
Beate Bollig
2014 J jnl
Implicit computation of maximum bipartite matchings by sublinear functional operations.
Theor. Comput. Sci.
Beate Bollig, Marc Gillé, Tobias Pröger
2014 J jnl
On efficient implicit OBDD-based algorithms for maximal matchings.
Inf. Comput.
Beate Bollig, Tobias Pröger
2014 — conf
On the Complexity of Some Ordering Problems.
MFCS (2)
Beate Bollig
2014 J jnl
On the Minimization of (Complete) Ordered Binary Decision Diagrams.
Electron. Colloquium Comput. Complex.
Beate Bollig
2014 C conf
On the Width of Ordered Binary Decision Diagrams.
COCOA
Beate Bollig
2013 J jnl
Priority functions for the approximation of the metric TSP.
Inf. Process. Lett.
Beate Bollig, Michael Capelle
2012 C conf
An Efficient Implicit OBDD-Based Algorithm for Maximal Matchings.
LATA
Beate Bollig, Tobias Pröger
2012 C conf
Implicit Computation of Maximum Bipartite Matchings by Sublinear Functional Operations.
TAMC
Beate Bollig, Marc Gillé, Tobias Pröger
2012 J jnl
On symbolic OBDD-based algorithms for the minimum spanning tree problem.
Theor. Comput. Sci.
Beate Bollig
2011 J jnl
Larger lower bounds on the OBDD complexity of integer multiplication.
Inf. Comput.
Beate Bollig
2011 J jnl
New Results on the Most Significant Bit of Integer Multiplication.
Theory Comput. Syst.
Beate Bollig, Jochen Klump
2011 J jnl
On the OBDD complexity of the most significant bit of integer multiplication.
Theor. Comput. Sci.
Beate Bollig
2011 B conf
Randomized OBDDs for the Most Significant Bit of Multiplication Need Exponential Size.
SOFSEM
Beate Bollig, Marc Gillé
2011 J jnl
Randomized OBDDs for the most significant bit of multiplication need exponential space.
Inf. Process. Lett.
Beate Bollig, Marc Gillé
2010 B conf
A Larger Lower Bound on the OBDD Complexity of the Most Significant Bit of Multiplication.
LATIN
Beate Bollig
2010 — ch.
Binary Decision Diagrams.
Boolean Models and Methods
Beate Bollig, Martin Sauerhoff, Detlef Sieling, Ingo Wegener, Yves Crama, Peter L. Hammer
2010 J jnl
Exact OBDD Bounds for Some Fundamental Functions.
Theory Comput. Syst.
Beate Bollig, Niko Range, Ingo Wegener
2010 B conf
Exponential Space Complexity for Symbolic Maximum Flow Algorithms in 0-1 Networks.
MFCS
Beate Bollig
2010 J jnl
Exponential space complexity for OBDD-based reachability analysis.
Inf. Process. Lett.
Beate Bollig
2010 — conf
On Symbolic OBDD-Based Algorithms for the Minimum Spanning Tree Problem.
COCOA (2)
Beate Bollig
2010 — conf
On Symbolic Representations of Maximum Matchings and (Un)directed Graphs.
IFIP TCS
Beate Bollig
2010 B conf
Symbolic OBDD-Based Reachability Analysis Needs Exponential Space.
SOFSEM
Beate Bollig
2009 J jnl
Integer Multiplicaton and the Complexity of Binary Decision Diagrams.
Bull. EATCS
Beate Bollig
2009 C conf
Larger Lower Bounds on the OBDD Complexity of Integer Multiplication.
LATA
Beate Bollig
2009 B conf
On the OBDD Complexity of Threshold Functions and the Variable Ordering Problem.
SOFSEM
Beate Bollig
2009 J jnl
On the size of (generalized) OBDDs for threshold functions.
Inf. Process. Lett.
Beate Bollig
2008 J jnl
A note on the size of OBDDs for the graph of integer multiplication.
Inf. Process. Lett.
Beate Bollig
2008 B conf
Exact OBDD Bounds for Some Fundamental Functions.
SOFSEM
Beate Bollig, Niko Range, Ingo Wegener
2008 B conf
New Results on the Most Significant Bit of Integer Multiplication.
ISAAC
Beate Bollig, Jochen Klump
2008 C conf
On the OBDD Complexity of the Most Significant Bit of Integer Multiplication.
TAMC
Beate Bollig
2008 J jnl
On the OBDD complexity of the most significant bit of integer multiplication.
Electron. Colloquium Comput. Complex.
Beate Bollig
2008 J jnl
The optimal read-once branching program complexity for the direct storage access function.
Inf. Process. Lett.
Beate Bollig
2007 J jnl
Exact OBDD Bounds for some Fundamental Functions.
Electron. Colloquium Comput. Complex.
Beate Bollig, Niko Range, Ingo Wegener
2007 J jnl
The Optimal Read-Once Branching Program Complexity for the Direct Storage Access Function.
Electron. Colloquium Comput. Complex.
Beate Bollig
2006 J jnl
Parity graph-driven read-once branching programs and an exponential lower bound for integer multiplication.
Theor. Comput. Sci.
Beate Bollig, Stephan Waack, Philipp Woelfel
2006 J jnl
Testing Membership in Formal Languages Implicitly Represented by Boolean Functions.
J. Univers. Comput. Sci.
Beate Bollig
2005 J jnl
A Lower Bound Technique for Nondeterministic Graph-Driven Read-Once-Branching Programs and Its Applications.
Theory Comput. Syst.
Beate Bollig, Philipp Woelfel
2005 J jnl
A large lower bound on the query complexity of a simple boolean function.
Inf. Process. Lett.
Beate Bollig
2005 B conf
Property Testing and the Branching Program Size of Boolean Functions.
FCT
Beate Bollig
2003 J jnl
A very simple function that requires exponential size nondeterministic graph-driven read-once branching programs.
Inf. Process. Lett.
Beate Bollig
2003 A conf
Complexity Theoretical Results on Nondeterministic Graph-Driven Read-Once Branching Programs.
STACS
Beate Bollig
2003 J jnl
Complexity Theoretical Results on Nondeterministic Graph-driven Read-Once Branching Programs.
RAIRO Theor. Informatics Appl.
Beate Bollig
2003 J jnl
Functions that have read-once branching programs of quadratic size are not necessarily testable.
Inf. Process. Lett.
Beate Bollig, Ingo Wegener
2002 B conf
A Lower Bound Technique for Nondeterministic Graph-Driven Read-Once-Branching Programs and Its Applications.
MFCS
Beate Bollig, Philipp Woelfel
2002 J jnl
A very simple function that requires exponential size nondeterministic graph-driven read-once branching programs
Electron. Colloquium Comput. Complex.
Beate Bollig
2002 J jnl
On the Nonapproximability of Boolean Functions by OBDDs and Read-k-Times Branching Programs.
Inf. Comput.
Beate Bollig, Martin Sauerhoff, Ingo Wegener
2002 — conf
Parity Graph-driven Read-Once Branching Programs and an Exponential Lower Bound for Integer Multiplication.
IFIP TCS
Beate Bollig, Stephan Waack, Philipp Woelfel
2001 A* conf
A read-once branching program lower bound of Omega(2
STOC
Beate Bollig, Philipp Woelfel
2001 A conf
On the Non-Approximability of Boolean Functions by OBDDs and Read-K-Times Branching Programs.
CCC
Beate Bollig, Martin Sauerhoff, Ingo Wegener
2001 J jnl
Parity Graph-driven Read-Once Branching Programs and an Exponential Lower Bound for Integer Multiplication
Electron. Colloquium Comput. Complex.
Beate Bollig, Philipp Woelfel, Stephan Waack
2001 J jnl
Restricted Nondeterministic Read-Once Branching Programs and an Exponential Lower Bound for Integer Multiplication.
RAIRO Theor. Informatics Appl.
Beate Bollig
2000 J jnl
Approximability and Nonapproximability by Binary Decision Diagrams
Electron. Colloquium Comput. Complex.
Beate Bollig, Ingo Wegener
2000 A* conf
Asymptotically Optimal Bounds for OBDDs and the Solution of Some Basic OBDD Problems.
ICALP
Beate Bollig, Ingo Wegener
2000 J jnl
Asymptotically Optimal Bounds for OBDDs and the Solution of Some Basic OBDD Problems.
J. Comput. Syst. Sci.
Beate Bollig, Ingo Wegener
2000 J jnl
Restricted Nondeterministic Read-Once Branching Programs and an Exponential Lower Bound for Integer Multiplication
Electron. Colloquium Comput. Complex.
Beate Bollig
2000 B conf
Restricted Nondeterministic Read-Once Branching Programs and an Exponential Lower Bound for Integer Multiplication.
MFCS
Beate Bollig
1999 J jnl
Asymptotically Optimal Bounds for OBDDs and the Solution of Some Basic OBDD Problems
Electron. Colloquium Comput. Complex.
Beate Bollig, Ingo Wegener
1999 J jnl
Complexity Theoretical Results on Partitioned (Nondeterministic) Binary Decision Diagrams.
Theory Comput. Syst.
Beate Bollig, Ingo Wegener
1999 J jnl
On the complexity of the hidden weighted bit function for various BDD models.
RAIRO Theor. Informatics Appl.
Beate Bollig, Martin Löbbing, Martin Sauerhoff, Ingo Wegener
1998 J jnl
A Very Simple Function that Requires Exponential Size Read-Once Branching Programs.
Inf. Process. Lett.
Beate Bollig, Ingo Wegener
1998 J jnl
Completeness and Non-Completeness Results with Respect to Read-Once Projections.
Inf. Comput.
Beate Bollig, Ingo Wegener
1998 J jnl
Hierarchy Theorems for
Theor. Comput. Sci.
Beate Bollig, Martin Sauerhoff, Detlef Sieling, Ingo Wegener
1998 — —
Komplexitätsanalysen für BDD-artige Datenstrukturen.
Beate Bollig
1997 B conf
Complexity Theoretical Results on Partitioned (Nondeterministic) Binary Decision Diagrams.
MFCS
Beate Bollig, Ingo Wegener
1996 J jnl
Improving the Variable Ordering of OBDDs Is NP-Complete.
IEEE Trans. Computers
Beate Bollig, Ingo Wegener
1996 J jnl
On the Effect of Local Changes in the Variable Ordering of Ordered Decision Diagrams.
Inf. Process. Lett.
Beate Bollig, Martin Löbbing, Ingo Wegener
1996 A conf
Read-once Projections and Formal Circuit Verification with Binary Decision Diagrams.
STACS
Beate Bollig, Ingo Wegener
1995 J jnl
On the Average Case Circuit Delay of Disjunction.
Parallel Process. Lett.
Beate Bollig, Martin Hühne, Stefan Pölt, Petr Savický
1995 J jnl
Read-once Projections and Formal Circuit Verification with Binary Decision Diagrams
Electron. Colloquium Comput. Complex.
Beate Bollig, Ingo Wegener
1994 J jnl
On the Power of Different Types of Restricted Branching Programs
Electron. Colloquium Comput. Complex.
Beate Bollig, Martin Sauerhoff, Detlef Sieling, Ingo Wegener