A linear time algorithm for maximum matchings in convex, bipartite graphs

DOI10.1016/0898-1221(96)00079-XzbMath0851.68090OpenAlexW2068928748MaRDI QIDQ1921260

Julian Scott Yeomans, George Steiner

Publication date: 25 November 1996

Published in: Computers \& Mathematics with Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0898-1221(96)00079-x

zbMATH Keywords

maximum matchingconvex bipartite graph

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (21)

A comment on ``A simple sequencing algorithm for mixed-model assembly lines in just-in-time production systems ⋮ Dynamic matchings in left vertex weighted convex bipartite graphs ⋮ A Linear-Time Algorithm for Maximum-Cardinality Matching on Cocomparability Graphs ⋮ Fast Dynamic Weight Matchings in Convex Bipartite Graphs ⋮ Induced matchings in strongly biconvex graphs and some algebraic applications ⋮ Routing equal-size messages on a slotted ring ⋮ The power of linear-time data reduction for maximum matching ⋮ The maximum fuzzy weighted matching models and hybrid genetic algorithm ⋮ Linear-time algorithm for the paired-domination problem in convex bipartite graphs ⋮ Finding maximum edge bicliques in convex bipartite graphs ⋮ Matchings in connection with ground delay program planning ⋮ Unnamed Item ⋮ Scalable parallel algorithms for maximum matching and Hamiltonian circuit in convex bipartite graphs ⋮ Mutual exclusion scheduling with interval graphs or related classes. I ⋮ On some graphs with a unique perfect matching ⋮ Algorithms for maximum independent set in convex bipartite graphs ⋮ The Power of Linear-Time Data Reduction for Maximum Matching ⋮ A new matrix bandwidth reduction algorithm ⋮ Computing maximum non-crossing matching in convex bipartite graphs ⋮ Optimal point movement for covering circular regions ⋮ Linear-time algorithms for maximum-weight induced matchings and minimum chain covers in convex bipartite graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on ``Scheduling unit-time tasks with integer release times and deadlines
• An 0(n log n) algorithm for the convex bipartite matching problem
• Efficient algorithms for finding maximum matchings in convex bipartite graphs and related problems
• Scheduling unit-time tasks with integer release times and deadlines
• A personnel assignment problem
• Level Schedules for Mixed-Model, Just-in-Time Processes
• Maximum matching in a convex bipartite graph

This page was built for publication: A linear time algorithm for maximum matchings in convex, bipartite graphs