On symbolic OBDD-based algorithms for the minimum spanning tree problem
From MaRDI portal
Publication:443706
DOI10.1016/j.tcs.2011.11.029zbMath1245.05125OpenAlexW2038076813MaRDI QIDQ443706
Publication date: 13 August 2012
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2011.11.029
ordered binary decision diagramstransitive closureminimum spanning tree algorithmssymbolic algorithms
Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Data structures (68P05)
Related Items
Randomized OBDD-based graph algorithms, On the OBDD representation of some graph classes, Randomized OBDD-Based Graph Algorithms, Priority functions for the approximation of the metric TSP, On the width of regular classes of finite structures
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the effect of local changes in the variable ordering of ordered decision diagrams
- On the size of binary decision diagrams representing Boolean functions
- Bisimulation minimization and symbolic model checking
- Representation of graphs by OBDDs
- On the OBDD size for graphs of bounded tree- and clique-width
- Symbolic model checking: \(10^{20}\) states and beyond
- Reduction of OBDDs in linear time
- Exponential space complexity for OBDD-based reachability analysis
- Symbolic topological sorting with OBDDs
- Symbolic graphs: Linear solutions to connectivity related problems
- An algorithm for strongly connected component analysis in \(n \log n\) symbolic steps
- On Symbolic Representations of Maximum Matchings and (Un)directed Graphs
- An optimal minimum spanning tree algorithm
- Succinct representations of graphs
- On the complexity of VLSI implementations and graph representations of Boolean functions with application to integer multiplication
- On the OBDD Complexity of the Most Significant Bit of Integer Multiplication
- Exponential Lower Bounds on the Space Complexity of OBDD-Based Graph Algorithms
- Exponential Space Complexity for Symbolic Maximum Flow Algorithms in 0-1 Networks
- Graph-Based Algorithms for Boolean Function Manipulation
- Implicat Representation of Graphs
- Finding Minimum Spanning Trees
- On the Complexity of the Hidden Weighted Bit Function for Various BDD Models
- A randomized linear-time algorithm to find minimum spanning trees
- A minimum spanning tree algorithm with inverse-Ackermann type complexity
- Branching Programs and Binary Decision Diagrams
- A note on succinct representations of graphs
- On the History of the Minimum Spanning Tree Problem
- Algorithms and Computation
- Mathematical Foundations of Computer Science 2003
- Graph-Theoretic Concepts in Computer Science
- SOFSEM 2006: Theory and Practice of Computer Science
- SOFSEM 2004: Theory and Practice of Computer Science
- Representing graphs implicitly using almost optimal space
- Minimum-weight spanning tree algorithms. A survey and empirical study
