Implicit computation of maximum bipartite matchings by sublinear functional operations

DOI10.1016/j.tcs.2014.07.020zbMath1303.68065OpenAlexW2176052300MaRDI QIDQ477185

Beate Bollig, Marc Gillé, Tobias Pröger

Publication date: 2 December 2014

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2014.07.020

zbMATH Keywords

ordered binary decision diagramsimplicit algorithmsmaximum bipartite matchings

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Data structures (68P05)

Related Items

Randomized OBDD-based graph algorithms, On the OBDD representation of some graph classes

Cites Work

• Unnamed Item
• Unnamed Item
• On the effect of local changes in the variable ordering of ordered decision diagrams
• An improvement of Goldberg, Plotkin and Vaidya's maximal node-disjoint paths algorithm
• Quality matching and local improvement for multilevel graph-partitioning
• Exponential space complexity for OBDD-based reachability analysis
• Complexity and modeling aspects of mesh refinement into quadrilaterals
• New results on the most significant bit of integer multiplication
• Symbolic topological sorting with OBDDs
• Symbolic graphs: Linear solutions to connectivity related problems
• An Efficient Implicit OBDD-Based Algorithm for Maximal Matchings
• On Symbolic OBDD-Based Algorithms for the Minimum Spanning Tree Problem
• On Symbolic Representations of Maximum Matchings and (Un)directed Graphs
• TWO THEOREMS IN GRAPH THEORY
• 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
• Branching Programs and Binary Decision Diagrams
• PARALLEL APPROXIMATE MATCHING
• Solving maximum flow problems on real-world bipartite graphs
• Power balance and apportionment algorithms for the United States Congress
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• SOFSEM 2006: Theory and Practice of Computer Science
• SOFSEM 2004: Theory and Practice of Computer Science