Randomized OBDD-based graph algorithms

DOI10.1007/978-3-319-25258-2_18MaRDI QIDQ3460720zbMATH OpenOpenAlexFDO

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

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20) Data structures (68P05)

Recommendations

• Randomized OBDD-based graph algorithms
• On efficient implicit OBDD-based algorithms for maximal matchings
• An efficient implicit OBDD-based algorithm for maximal matchings
• OBDD-based representation of interval graphs
• On the OBDD representation of some graph classes

Cites work

• scientific article; zbMATH DE number 2079387 (Why is no real title available?)
• scientific article; zbMATH DE number 910866 (Why is no real title available?)
• A Simple Parallel Algorithm for the Maximal Independent Set Problem
• A fast and simple randomized parallel algorithm for maximal matching
• A fast and simple randomized parallel algorithm for the maximal independent set problem
• Almost \(k\)-wise independence and hard Boolean functions.
• An algorithm for strongly connected component analysis in \(n \log n\) symbolic steps
• An optimal bit complexity randomized distributed MIS algorithm
• Branching Programs and Binary Decision Diagrams
• Entropy of contact circuits and lower bounds on their complexity
• Exponential Lower Bounds on the Space Complexity of OBDD-Based Graph Algorithms
• Graph-Based Algorithms for Boolean Function Manipulation
• Implicit computation of maximum bipartite matchings by sublinear functional operations
• Improved boolean formulas for the Ramsey graphs
• Locality in Distributed Graph Algorithms
• OBDD-based representation of interval graphs
• On efficient implicit OBDD-based algorithms for maximal matchings
• On symbolic OBDD-based algorithms for the minimum spanning tree problem
• On the OBDD size for graphs of bounded tree- and clique-width
• On the effect of local changes in the variable ordering of ordered decision diagrams
• On the power of two-point based sampling
• Priority functions for the approximation of the metric TSP
• Representation of graphs by OBDDs
• SOFSEM 2004: Theory and Practice of Computer Science
• SOFSEM 2006: Theory and Practice of Computer Science
• Simple Constructions of Almost k-wise Independent Random Variables
• Small-Bias Probability Spaces: Efficient Constructions and Applications
• Symbolic graphs: Linear solutions to connectivity related problems
• Symbolic model checking: \(10^{20}\) states and beyond
• Symbolic topological sorting with OBDDs
• The University of Florida sparse matrix collection
• The size of reduced OBDD's and optimal read-once branching programs for almost all Boolean functions
• The space complexity of approximating the frequency moments

Cited in

(9)

• On symbolic representations of maximum matchings and (Un)directed graphs
• OBDD-based representation of interval graphs
• Random iteration algorithm for graph-directed sets
• An efficient implicit OBDD-based algorithm for maximal matchings
• Randomized OBDD-based graph algorithms
• Introduction to the OBDD algorithm for the ATP community
• Implicit computation of maximum bipartite matchings by sublinear functional operations
• Implicit computation of maximum bipartite matchings by sublinear functional operations
• On efficient implicit OBDD-based algorithms for maximal matchings

Describes a project that uses

Uses Software

• SparseMatrix

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)