Randomized OBDD-based graph algorithms
type: Item
instance of: scholarly article
title: Randomized OBDD-based graph algorithms
zbMATH Open document ID: 1407.68533
author: Marc Bury
published in: Theoretical Computer Science
publication date: 2018-11-29T00:00:00Z
Mathematics Subject Classification ID: 68W20
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68P05
zbMATH DE Number: 6986762
zbMATH Keywords: ordered binary decision diagram
zbMATH Keywords: \(k\)-wise independence
zbMATH Keywords: almost \(k\)-wise independence
zbMATH Keywords: matching
zbMATH Keywords: minimum spanning tree
zbMATH Keywords: randomized implicit algorithm
describes a project that uses: SparseMatrix
MaRDI profile type: Publication
full work available at URL: j.tcs.2016.11.028
OpenAlex ID: W2552670115
cites work: A fast and simple randomized parallel algorithm for the maximal independent set problem
cites work: Simple Constructions of Almost k-wise Independent Random Variables
cites work: Almost \(k\)-wise independence versus \(k\)-wise independence
cites work: The space complexity of approximating the frequency moments
cites work: An algorithm for strongly connected component analysis in \(n \log n\) symbolic steps
cites work: On symbolic OBDD-based algorithms for the minimum spanning tree problem
cites work: Priority functions for the approximation of the metric TSP
cites work: Implicit computation of maximum bipartite matchings by sublinear functional operations
cites work: On the effect of local changes in the variable ordering of ordered decision diagrams
cites work: On efficient implicit OBDD-based algorithms for maximal matchings
cites work: Graph-Based Algorithms for Boolean Function Manipulation
cites work: Symbolic model checking: \(10^{20}\) states and beyond
cites work: On the power of two-point based sampling
cites work: Q3651735
cites work: Q4886040
cites work: The university of Florida sparse matrix collection
cites work: Q4471346
cites work: Symbolic graphs: Linear solutions to connectivity related problems
cites work: OBDD-Based Representation of Interval Graphs
cites work: Q4843270
cites work: A fast and simple randomized parallel algorithm for maximal matching
cites work: On a set of almost deterministic k-independent random variables
cites work: Entropy of contact circuits and lower bounds on their complexity
cites work: Almost \(k\)-wise independence and hard Boolean functions.
cites work: A randomized linear-time algorithm to find minimum spanning trees
cites work: Locality in Distributed Graph Algorithms
cites work: A Simple Parallel Algorithm for the Maximal Independent Set Problem
cites work: On the OBDD size for graphs of bounded tree- and clique-width
cites work: An optimal bit complexity randomized distributed MIS algorithm
cites work: Probability and Computing
cites work: The probabilistic method yields deterministic parallel algorithms
cites work: Small-Bias Probability Spaces: Efficient Constructions and Applications
cites work: Solving maximum flow problems on real-world bipartite graphs
cites work: Representation of graphs by OBDDs
cites work: Improved boolean formulas for the Ramsey graphs
cites work: SOFSEM 2004: Theory and Practice of Computer Science
cites work: SOFSEM 2006: Theory and Practice of Computer Science
cites work: Exponential Lower Bounds on the Space Complexity of OBDD-Based Graph Algorithms
cites work: On Universal Classes of Extremely Random Constant-Time Hash Functions
cites work: The size of reduced OBDD's and optimal read-once branching programs for almost all Boolean functions
cites work: Branching Programs and Binary Decision Diagrams
cites work: New hash functions and their use in authentication and set equality
cites work: Symbolic topological sorting with OBDDs
DOI: 10.1016/J.TCS.2016.11.028
description: scientific article; zbMATH DE number 6986762