Using relations to develop a Haskell program for computing maximum bipartite matchings

DOI10.1007/978-3-642-33314-9_9MaRDI QIDQ2915140zbMATH OpenOpenAlexFDO

Authors Nikita Danilenko

Publication date 21 September 2012

Published in Relational and Algebraic Methods in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-33314-9_9

Mathematics Subject Classification ID

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

Recommendations

• A play on regular expressions: functional pearl
• Implicit computation of maximum bipartite matchings by sublinear functional operations
• Implicit computation of maximum bipartite matchings by sublinear functional operations
• Semigroupoid Interfaces for Relation-Algebraic Programming in Haskell
• Computing a maximum cardinality matching in a bipartite graph in time \(O(n^{1,5}\sqrt{m/\log \,n})\)

Cites work

• A functional, successor list based version of Warshall's algorithm with applications
• Algorithms – ESA 2004
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• An approach to fast arrays in Haskell
• Efficient graph algorithms using lazy monolithic arrays
• Functional programming with graphs
• scientific article; zbMATH DE number 876677 (Why is no real title available?)
• Inductive graphs and functional graph algorithms
• Orders, lattices and relations with applications
• TWO THEOREMS IN GRAPH THEORY

Cited in

(3)

• Combining relation algebra and data refinement to develop rectangle-based functional programs for reflexive-transitive closures
• Simple rectangle-based functional programs for computing reflexive-transitive closures
• Cardinality of relations with applications

Describes a project that uses

Uses Software

• Haskell

This page was built for publication: Using relations to develop a Haskell program for computing maximum bipartite matchings

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