Fast dynamic weight matchings in convex bipartite graphs

DOI10.1007/978-3-662-48054-0_50MaRDI QIDQ2946428zbMATH OpenOpenAlexFDO

Authors

Publication date 16 September 2015

Published in Mathematical Foundations of Computer Science 2015 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-662-48054-0_50

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Signed and weighted graphs (05C22) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• Dynamic Matchings in Left Weighted Convex Bipartite Graphs
• Dynamic matchings in left vertex weighted convex bipartite graphs
• Dynamic Matchings in Convex Bipartite Graphs
• Matchings in node-weighted convex bipartite graphs
• Fully dynamic matching in bipartite graphs

Cites work

• scientific article; zbMATH DE number 3902700 (Why is no real title available?)
• A linear time algorithm for maximum matchings in convex, bipartite graphs
• Dynamic Matchings in Convex Bipartite Graphs
• Dynamic Matchings in Left Weighted Convex Bipartite Graphs
• Matchings in node-weighted convex bipartite graphs
• Maximum matching in a convex bipartite graph
• Optimal assignments in an ordered set: An application of matroid theory
• Preserving order in a forest in less than logarithmic time and linear space
• Vertex-Weighted Matching in Two-Directional Orthogonal Ray Graphs

Cited in

(8)

• Bipartite matching with linear edge weights
• Dynamic Matchings in Left Weighted Convex Bipartite Graphs
• Dynamic Matchings in Convex Bipartite Graphs
• Incremental assignment problem
• Dynamic matchings in left vertex weighted convex bipartite graphs
• Fast primal-dual update against local weight update in linear assignment problem and its application
• Matchings in node-weighted convex bipartite graphs
• Linear-time algorithms for maximum-weight induced matchings and minimum chain covers in convex bipartite graphs

This page was built for publication: Fast dynamic weight matchings in convex bipartite graphs

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