Implicit computation of maximum bipartite matchings by sublinear functional operations

DOI10.1016/J.TCS.2014.07.020MaRDI QIDQ477185zbMATH OpenOpenAlexFDO

Authors 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

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

Recommendations

• Implicit computation of maximum bipartite matchings by sublinear functional operations
• An efficient implicit OBDD-based algorithm for maximal matchings
• On efficient implicit OBDD-based algorithms for maximal matchings
• scientific article; zbMATH DE number 5909229
• Randomized OBDD-based graph algorithms

Cites work

• scientific article; zbMATH DE number 2079387 (Why is no real title available?)
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• An efficient implicit OBDD-based algorithm for maximal matchings
• An improvement of Goldberg, Plotkin and Vaidya's maximal node-disjoint paths algorithm
• Branching Programs and Binary Decision Diagrams
• Complexity and modeling aspects of mesh refinement into quadrilaterals
• Exponential Lower Bounds on the Space Complexity of OBDD-Based Graph Algorithms
• Exponential Space Complexity for Symbolic Maximum Flow Algorithms in 0-1 Networks
• Exponential space complexity for OBDD-based reachability analysis
• Graph-Based Algorithms for Boolean Function Manipulation
• Network flows. Theory, algorithms, and applications.
• New results on the most significant bit of integer multiplication
• On symbolic OBDD-based algorithms for the minimum spanning tree problem
• On symbolic representations of maximum matchings and (Un)directed graphs
• On the effect of local changes in the variable ordering of ordered decision diagrams
• PARALLEL APPROXIMATE MATCHING
• Power balance and apportionment algorithms for the United States Congress
• Quality matching and local improvement for multilevel graph-partitioning
• SOFSEM 2004: Theory and Practice of Computer Science
• SOFSEM 2006: Theory and Practice of Computer Science
• Solving maximum flow problems on real-world bipartite graphs
• Sublinear-Time Parallel Algorithms for Matching and Related Problems
• Symbolic graphs: Linear solutions to connectivity related problems
• Symbolic topological sorting with OBDDs
• TWO THEOREMS IN GRAPH THEORY

Cited in

(6)

• Using relations to develop a Haskell program for computing maximum bipartite matchings
• An efficient implicit OBDD-based algorithm for maximal matchings
• On the OBDD representation of some graph classes
• Randomized OBDD-based graph algorithms
• Implicit computation of maximum bipartite matchings by sublinear functional operations
• On efficient implicit OBDD-based algorithms for maximal matchings

This page was built for publication: Implicit computation of maximum bipartite matchings by sublinear functional operations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q477185)