Randomized OBDD-based graph algorithms
From MaRDI portal
Publication:3460720
DOI10.1007/978-3-319-25258-2_18zbMATH Open1407.68532OpenAlexW2295004524MaRDI QIDQ3460720FDOQ3460720
Authors: Marc Bury 
Publication date: 8 January 2016
Published in: Structural Information and Communication Complexity (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-319-25258-2_18
Recommendations
Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20) Data structures (68P05)
Cites Work
- The University of Florida sparse matrix collection
- Graph-Based Algorithms for Boolean Function Manipulation
- The space complexity of approximating the frequency moments
- Symbolic model checking: \(10^{20}\) states and beyond
- Small-Bias Probability Spaces: Efficient Constructions and Applications
- Simple Constructions of Almost k-wise Independent Random Variables
- Branching Programs and Binary Decision Diagrams
- Entropy of contact circuits and lower bounds on their complexity
- A Simple Parallel Algorithm for the Maximal Independent Set Problem
- A fast and simple randomized parallel algorithm for the maximal independent set problem
- Locality in Distributed Graph Algorithms
- An algorithm for strongly connected component analysis in \(n \log n\) symbolic steps
- On the effect of local changes in the variable ordering of ordered decision diagrams
- On the power of two-point based sampling
- Representation of graphs by OBDDs
- On the OBDD size for graphs of bounded tree- and clique-width
- Priority functions for the approximation of the metric TSP
- Symbolic topological sorting with OBDDs
- Symbolic graphs: Linear solutions to connectivity related problems
- Exponential Lower Bounds on the Space Complexity of OBDD-Based Graph Algorithms
- On symbolic OBDD-based algorithms for the minimum spanning tree problem
- Title not available (Why is that?)
- On efficient implicit OBDD-based algorithms for maximal matchings
- SOFSEM 2006: Theory and Practice of Computer Science
- SOFSEM 2004: Theory and Practice of Computer Science
- An optimal bit complexity randomized distributed MIS algorithm
- A fast and simple randomized parallel algorithm for maximal matching
- Implicit computation of maximum bipartite matchings by sublinear functional operations
- The size of reduced OBDD's and optimal read-once branching programs for almost all Boolean functions
- OBDD-based representation of interval graphs
- Title not available (Why is that?)
- Almost \(k\)-wise independence and hard Boolean functions.
- Improved boolean formulas for the Ramsey graphs
Cited In (9)
- Random iteration algorithm for graph-directed sets
- Implicit computation of maximum bipartite matchings by sublinear functional operations
- On efficient implicit OBDD-based algorithms for maximal matchings
- OBDD-based representation of interval graphs
- Implicit computation of maximum bipartite matchings by sublinear functional operations
- On symbolic representations of maximum matchings and (Un)directed graphs
- Randomized OBDD-based graph algorithms
- Introduction to the OBDD algorithm for the ATP community
- An efficient implicit OBDD-based algorithm for maximal matchings
Uses Software
This page was built for publication: Randomized OBDD-based graph algorithms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3460720)
