On efficient implicit OBDD-based algorithms for maximal matchings

DOI10.1016/j.ic.2014.08.006zbMath1309.68056OpenAlexW2060981730MaRDI QIDQ476163

Beate Bollig, Tobias Pröger

Publication date: 28 November 2014

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2014.08.006

zbMATH Keywords

ordered binary decision diagramsimplicit graph algorithmsmaximal matchings

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Data structures (68P05)

Related Items (3)

Randomized OBDD-based graph algorithms ⋮ On the OBDD representation of some graph classes ⋮ Randomized OBDD-Based Graph Algorithms

Cites Work

• 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
• Representation of graphs by OBDDs
• On the OBDD size for graphs of bounded tree- and clique-width
• An optimal parallel algorithm for maximal matching
• Exponential space complexity for OBDD-based reachability analysis
• Priority functions for the approximation of the metric TSP
• Symbolic topological sorting with OBDDs
• Symbolic graphs: Linear solutions to connectivity related problems
• An Efficient Implicit OBDD-Based Algorithm for Maximal Matchings
• Implicit Computation of Maximum Bipartite Matchings by Sublinear Functional Operations
• On Symbolic OBDD-Based Algorithms for the Minimum Spanning Tree Problem
• On Symbolic Representations of Maximum Matchings and (Un)directed Graphs
• On the complexity of VLSI implementations and graph representations of Boolean functions with application to 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
• Sublinear-Time Parallel Algorithms for Matching and Related Problems
• On the Complexity of the Hidden Weighted Bit Function for Various BDD Models
• Branching Programs and Binary Decision Diagrams
• Heuristic initialization for bipartite matching problems
• SOFSEM 2006: Theory and Practice of Computer Science
• SOFSEM 2004: Theory and Practice of Computer Science

This page was built for publication: On efficient implicit OBDD-based algorithms for maximal matchings