A fast bipartite network flow algorithm for selective assembly

DOI10.1016/S0167-6377(98)00017-0zbMath0911.90209WikidataQ127673574 ScholiaQ127673574MaRDI QIDQ1273091

S. Thomas McCormick, Tomomi Matsui, Satoru Iwata

Publication date: 6 December 1998

Published in: Operations Research Letters (Search for Journal in Brave)

zbMATH Keywords

bipartite graphsnetwork flowpreemptive schedulinglinear-time algorithmMonge propertyselective assemblybipartite network flowearliest due date

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Deterministic scheduling theory in operations research (90B35) Deterministic network models in operations research (90B10)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Monge and feasibility sequences in general flow problems
• An 0(n log n) algorithm for the convex bipartite matching problem
• Monge sequences, antimatroids, and the transportation problem with forbidden arcs
• A linear-time algorithm for a special case of disjoint set union
• Efficient algorithms for finding maximum matchings in convex bipartite graphs and related problems
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Scheduling jobs to minimize total cost
• Matching problems in selective assembly operations
• Perspectives of Monge properties in optimization
• Some simple scheduling algorithms
• Maximum matching in a convex bipartite graph
• Scheduling Jobs on Several Machines with the Job Splitting Property