Implicit Computation of Maximum Bipartite Matchings by Sublinear Functional Operations

DOI10.1007/978-3-642-29952-0_45zbMath1354.05128OpenAlexW2122890833MaRDI QIDQ2898059

Marc Gillé, Beate Bollig, Tobias Pröger

Publication date: 16 July 2012

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-29952-0_45

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) 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 ⋮ Priority functions for the approximation of the metric TSP ⋮ On efficient implicit OBDD-based algorithms for maximal matchings

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
• 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
• Using Interior-Point Methods for Fast Parallel Algorithms for Bipartite Matching and Related Problems
• 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

This page was built for publication: Implicit Computation of Maximum Bipartite Matchings by Sublinear Functional Operations