The Complexity of Problems on Graphs Represented as OBDDs

No abstract is available for this paper.

• Publication year

  1998

• Venue

  Chicago journal of theoretical computer science

• Publication date

  1998-02-25

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1007/BFB0028563
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• How to encode a logical structure by an OBDD

  1998cited by this paper
• Languages Represented by Boolean Formulas

  1997cited by this paper
• Workshop Summary: Computational and Complexity Issues in Automated Verification

  1996cited by this paper
• The Complexity of Searching Implicit Graphs

  1996cited by this paper
• Module Checking

  1996cited by this paper
• Succinct representation, leaf languages, and projection reductions

  1996cited by this paper
• Restricted branching programs and hardware verification

  1995cited by this paper
• A lower bound for integer multiplication with read-once branching programs

  1995cited by this paper
• Methodology and System for Practical Formal Verification of Reactive Hardware

  1994cited by this paper
• The complexity of verification

  1994cited by this paper
• Symbolic Model Checking

  1993cited by this paper
• Verification of the Futurebus+ cache coherence protocol

  1993cited by this paper
• Symbolic Boolean manipulation with ordered binary-decision diagrams

  1992cited by this paper
• Symbolic model checking

  1992cited by this paper
• The complexity of algorithmic problems on succinct instances

  1992cited by this paper
• Symbolic Model Checking: 10^20 States and Beyond

  1990cited by this paper
• The Complexity of Graph Problems for Succinctly Represented Graphs

  1990cited by this paper
• Ordered binary decision diagrams and circuit structure

  1989cited by this paper
• Symbolic model checking: 1020 states and beyond

  1989cited by this paper
• Graph-based Algorithm for Boolean Function Manipulation

  1989influential reference
• Succinct Representations of Counting Problems

  1988cited by this paper
• Efficient Model Checking in Fragments of the Propositional Mu-Calculus (Extended Abstract)

  1986cited by this paper
• A Note on Succinct Representations of Graphs

  1986cited by this paper
• Succinct Representations of Graphs

  1984cited by this paper
• A complexity theory based on Boolean algebra

  1981cited by this paper
• Introduction to Automata Theory, Languages and Computation

  1979cited by this paper
• The complexity of theorem-proving procedures

  1971cited by this paper

• Numerical Errors in Quantitative System Analysis With Decision Diagrams

  2025cites this paper
• Automated Reasoning in Quantum Circuit Compilation

  2024cites this paper
• Checking LTL[F,G,X] on compressed traces in polynomial time

  2021cites this paper
• Data race detection on compressed traces

  2018cites this paper
• Sequential Relational Decomposition

  2018cites this paper
• On graph algorithms for large-scale graphs

  2015cites this paper
• On the Complexity of Symbolic Verification and Decision Problems in Bit-Vector Logic

  2014cites this paper
• Succinct Encodings of Graph Isomorphism

  2014cites this paper
• Processing Succinct Matrices and Vectors

  2014cites this paper
• On efficient implicit OBDD-based algorithms for maximal matchings

  2014cites this paper
• OBDD-Based Representation of Interval Graphs

  2013cites this paper
• A uniform approach to the complexity and analysis of succinct systems

  2012cites this paper
• Représentations des polynômes, algorithmes et bornes inférieures

  2012cites this paper
• Implicit computation of maximum bipartite matchings by sublinear functional operations

  2012cites this paper
• On symbolic OBDD-based algorithms for the minimum spanning tree problem

  2010cites this paper
• On Symbolic Representations of Maximum Matchings and (Un)directed Graphs

  2010cites this paper
• On the size of data structures used in symbolic model checking

  2010cites this paper
• Exponential Space Complexity for Symbolic Maximum Flow Algorithms in 0-1 Networks

  2010cites this paper
• Searching Trees: An Essay

  2009cites this paper
• Symbolic Graphs: Linear Solutions to Connectivity Related Problems

  2007influential citation
• Implicit Simulation of FNC Algorithms

  2007influential citation
• A parametric analysis of the state-explosion problem in model checking

  2006cites this paper
• On the OBDD size for graphs of bounded tree- and clique-width

  2006cites this paper
• The Complexity of Problems on Implicitly Represented Inputs

  2006influential citation
• Exponential Lower Bounds on the Space Complexity of OBDD-Based Graph Algorithms

  2006cites this paper
• Word Problems and Membership Problems on Compressed Words

  2006cites this paper
• Lower Bounds on the OBDD Size of Graphs of Some Popular Functions

  2005cites this paper
• Model-checking hierarchical structures

  2005cites this paper
• Graph Algorithms for Massive Data-Sets

  2005influential citation
• BDDs--design, analysis, complexity, and applications

  2004cites this paper
• A Complete Bibliography of Publications in Chicago Journal of Theoretical Computer Science

  2004cites this paper
• A Symbolic Approach to the All-Pairs Shortest-Paths Problem

  2004cites this paper
• Computing minimal changes of models of systems

  2003cites this paper
• Counterexample-guided abstraction refinement for symbolic model checking

  2003cites this paper
• Symbolic topological sorting with OBDDs

  2003cites this paper
• A Parametric Analysis of the State Explosion Problem in Model Checking

  2002cites this paper
• Progress on the State Explosion Problem in Model Checking

  2001cites this paper
• Planning with Resources and Concurrency: A Forward Chaining Approach

  2001cites this paper
• The Complexity of Some Basic Problems for Dynamic Process Graphs

  2001cites this paper
• Complexity of Probabilistic Planning under Average Rewards

  2001cites this paper
• Model Checking with Finite Complete Prefixes Is PSPACE-Complete

  2000cites this paper
• Participatory Simulations: Building Collaborative Understanding Through Immersive Dynamic Modeling

  2000cites this paper
• Definability and Compression

  2000cites this paper
• Symbolic model checking for µ-calculus requires exponential time

  2000cites this paper
• Query optimization for selections using bitmaps

  1999cites this paper
• Restrictive Acceptance Suffices for Equivalence Problems

  1999cites this paper