An algorithm to solve them ×n assignment problem in expected timeO(mn logn)

DOI10.1002/NET.3230100205zbMATH Open0441.68076OpenAlexW1993343369MaRDI QIDQ3883530FDOQ3883530

Richard Karp

Publication date: 1980

Published in: Networks (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/net.3230100205

zbMATH Keywords

assignment problempriority queuesedge costs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Deterministic network models in operations research (90B10) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Cites Work

• Title not available (Why is that?)

Cited In (10)

• Selected topics on assignment problems
• Recent developments in information-based complexity
• Average complexity of divide-and-conquer algorithms
• Random assignment problems
• The random linear bottleneck assignment problem
• A comparison of two algorithms for the assignment problem
• Average case optimality
• A BRANCH-AND-BOUND ALGORITHM FOR FINDING ALL OPTIMAL SOLUTIONS OF THE ASSIGNMENT PROBLEM
• A shortest augmenting path algorithm for dense and sparse linear assignment problems
• MetaCoAG: binning metagenomic contigs via composition, coverage and assembly graphs

This page was built for publication: An algorithm to solve them ×n assignment problem in expected timeO(mn logn)

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