Implicit computation of maximum bipartite matchings by sublinear functional operations
From MaRDI portal
Publication:477185
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
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
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
