Beate Bollig

According to our database, Beate Bollig authored at least 55 papers between 1994 and 2021.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of three.

2021

On the Relation Between Structured d-DNNFs and SDDs.

Beate Bollig, Martin Farenholtz

Theory Comput. Syst., 2021

2020

On Limitations of Structured (Deterministic) DNNFs.

Beate Bollig, Matthias Buttkus

Theory Comput. Syst., 2020

2019

On the Relative Succinctness of Sentential Decision Diagrams.

Beate Bollig, Matthias Buttkus

Theory Comput. Syst., 2019

2016

On the Minimization of (Complete) Ordered Binary Decision Diagrams.

Beate Bollig

Theory Comput. Syst., 2016

On the OBDD representation of some graph classes.

Beate Bollig, Marc Bury

Discret. Appl. Math., 2016

2014

A simpler counterexample to a long-standing conjecture on the complexity of Bryant's apply algorithm.

Beate Bollig

Inf. Process. Lett., 2014

On efficient implicit OBDD-based algorithms for maximal matchings.

Beate Bollig, Tobias Pröger

Inf. Comput., 2014

On the Complexity of Some Ordering Problems.

Beate Bollig

Proceedings of the Mathematical Foundations of Computer Science 2014, 2014

On the Width of Ordered Binary Decision Diagrams.

Beate Bollig

Proceedings of the Combinatorial Optimization and Applications, 2014

2013

Priority functions for the approximation of the metric TSP.

Beate Bollig, Michael Capelle

Inf. Process. Lett., 2013

2012

Implicit Computation of Maximum Bipartite Matchings by Sublinear Functional Operations.

Beate Bollig, Marc Gillé, Tobias Pröger

Proceedings of the Theory and Applications of Models of Computation, 2012

An Efficient Implicit OBDD-Based Algorithm for Maximal Matchings.

Beate Bollig, Tobias Pröger

Proceedings of the Language and Automata Theory and Applications, 2012

2011

Randomized OBDDs for the most significant bit of multiplication need exponential space.

Beate Bollig, Marc Gillé

Inf. Process. Lett., 2011

Randomized OBDDs for the Most Significant Bit of Multiplication Need Exponential Size.

Beate Bollig, Marc Gillé

Proceedings of the SOFSEM 2011: Theory and Practice of Computer Science, 2011

2010

Exponential space complexity for OBDD-based reachability analysis.

Beate Bollig

Inf. Process. Lett., 2010

Symbolic OBDD-Based Reachability Analysis Needs Exponential Space.

Beate Bollig

Proceedings of the SOFSEM 2010: Theory and Practice of Computer Science, 2010

Exponential Space Complexity for Symbolic Maximum Flow Algorithms in 0-1 Networks.

Beate Bollig

Proceedings of the Mathematical Foundations of Computer Science 2010, 2010

A Larger Lower Bound on the OBDD Complexity of the Most Significant Bit of Multiplication.

Beate Bollig

Proceedings of the LATIN 2010: Theoretical Informatics, 2010

On Symbolic Representations of Maximum Matchings and (Un)directed Graphs.

Beate Bollig

Proceedings of the Theoretical Computer Science, 2010

On Symbolic OBDD-Based Algorithms for the Minimum Spanning Tree Problem.

Beate Bollig

Proceedings of the Combinatorial Optimization and Applications, 2010

Binary Decision Diagrams.

Beate Bollig, Martin Sauerhoff, Detlef Sieling, Ingo Wegener, Yves Crama, Peter L. Hammer

Proceedings of the Boolean Models and Methods in Mathematics, 2010

2009

On the size of (generalized) OBDDs for threshold functions.

Beate Bollig

Inf. Process. Lett., 2009

Integer Multiplicaton and the Complexity of Binary Decision Diagrams.

Beate Bollig

Bull. EATCS, 2009

On the OBDD Complexity of Threshold Functions and the Variable Ordering Problem.

Beate Bollig

Proceedings of the SOFSEM 2009: Theory and Practice of Computer Science, 2009

Larger Lower Bounds on the OBDD Complexity of Integer Multiplication.

Beate Bollig

Proceedings of the Language and Automata Theory and Applications, 2009

2008

A note on the size of OBDDs for the graph of integer multiplication.

Beate Bollig

Inf. Process. Lett., 2008

On the OBDD Complexity of the Most Significant Bit of Integer Multiplication.

Beate Bollig

Proceedings of the Theory and Applications of Models of Computation, 2008

Exact OBDD Bounds for Some Fundamental Functions.

Beate Bollig, Niko Range, Ingo Wegener

Proceedings of the SOFSEM 2008: Theory and Practice of Computer Science, 2008

New Results on the Most Significant Bit of Integer Multiplication.

Beate Bollig, Jochen Klump

Proceedings of the Algorithms and Computation, 19th International Symposium, 2008

2007

The Optimal Read-Once Branching Program Complexity for the Direct Storage Access Function.

Beate Bollig

Electron. Colloquium Comput. Complex., 2007

2006

Testing Membership in Formal Languages Implicitly Represented by Boolean Functions.

Beate Bollig

J. Univers. Comput. Sci., 2006

2005

A large lower bound on the query complexity of a simple boolean function.

Beate Bollig

Inf. Process. Lett., 2005

Property Testing and the Branching Program Size of Boolean Functions.

Beate Bollig

Proceedings of the Fundamentals of Computation Theory, 15th International Symposium, 2005

2003

Functions that have read-once branching programs of quadratic size are not necessarily testable.

Beate Bollig, Ingo Wegener

Inf. Process. Lett., 2003

Complexity Theoretical Results on Nondeterministic Graph-Driven Read-Once Branching Programs.

Beate Bollig

Proceedings of the STACS 2003, 20th Annual Symposium on Theoretical Aspects of Computer Science, Berlin, Germany, February 27, 2003

2002

On the Nonapproximability of Boolean Functions by OBDDs and Read-k-Times Branching Programs.

Beate Bollig, Martin Sauerhoff, Ingo Wegener

Inf. Comput., 2002

A very simple function that requires exponential size nondeterministic graph-driven read-once branching programs

Beate Bollig

Electron. Colloquium Comput. Complex., 2002

A Lower Bound Technique for Nondeterministic Graph-Driven Read-Once-Branching Programs and Its Applications.

Beate Bollig, Philipp Woelfel

Proceedings of the Mathematical Foundations of Computer Science 2002, 2002

Parity Graph-driven Read-Once Branching Programs and an Exponential Lower Bound for Integer Multiplication.

Beate Bollig, Stephan Waack, Philipp Woelfel

Proceedings of the Foundations of Information Technology in the Era of Networking and Mobile Computing, 2002

2001

A read-once branching program lower bound of Omega(2^n/4) for integer multiplication using universal.

Beate Bollig, Philipp Woelfel

Proceedings of the Proceedings on 33rd Annual ACM Symposium on Theory of Computing, 2001

On the Non-Approximability of Boolean Functions by OBDDs and Read-K-Times Branching Programs.

Beate Bollig, Martin Sauerhoff, Ingo Wegener

Proceedings of the 16th Annual IEEE Conference on Computational Complexity, 2001

2000

Approximability and Nonapproximability by Binary Decision Diagrams

Beate Bollig, Ingo Wegener

Electron. Colloquium Comput. Complex., 2000

Restricted Nondeterministic Read-Once Branching Programs and an Exponential Lower Bound for Integer Multiplication.

Beate Bollig

Proceedings of the Mathematical Foundations of Computer Science 2000, 2000

Asymptotically Optimal Bounds for OBDDs and the Solution of Some Basic OBDD Problems.

Beate Bollig, Ingo Wegener

Proceedings of the Automata, Languages and Programming, 27th International Colloquium, 2000

1999

On the complexity of the hidden weighted bit function for various BDD models.

Beate Bollig, Martin Löbbing, Martin Sauerhoff, Ingo Wegener

RAIRO Theor. Informatics Appl., 1999

1998

Komplexitätsanalysen für BDD-artige Datenstrukturen.

Beate Bollig

PhD thesis, 1998

Hierarchy Theorems for <i>k</i>OBDDs and <i>k</i>IBDDs.

Beate Bollig, Martin Sauerhoff, Detlef Sieling, Ingo Wegener

Theor. Comput. Sci., 1998

A Very Simple Function that Requires Exponential Size Read-Once Branching Programs.

Beate Bollig, Ingo Wegener

Inf. Process. Lett., 1998

Completeness and Non-Completeness Results with Respect to Read-Once Projections.

Beate Bollig, Ingo Wegener

Inf. Comput., 1998

1997

Complexity Theoretical Results on Partitioned (Nondeterministic) Binary Decision Diagrams.

Beate Bollig, Ingo Wegener

Proceedings of the Mathematical Foundations of Computer Science 1997, 1997

1996

Improving the Variable Ordering of OBDDs Is NP-Complete.

Beate Bollig, Ingo Wegener

IEEE Trans. Computers, 1996

On the Effect of Local Changes in the Variable Ordering of Ordered Decision Diagrams.

Beate Bollig, Martin Löbbing, Ingo Wegener

Inf. Process. Lett., 1996

Read-once Projections and Formal Circuit Verification with Binary Decision Diagrams.

Beate Bollig, Ingo Wegener

Proceedings of the STACS 96, 1996

1995

On the Average Case Circuit Delay of Disjunction.

Beate Bollig, Martin Hühne, Stefan Pölt, Petr Savický

Parallel Process. Lett., 1995

1994

On the Power of Different Types of Restricted Branching Programs

Beate Bollig, Martin Sauerhoff, Detlef Sieling, Ingo Wegener

Electron. Colloquium Comput. Complex., 1994