Solving a combinatorial problem with network flows

DOI10.1007/BF02936064MaRDI QIDQ1767398zbMATH OpenOpenAlexFDO

Authors Florin Manea, Călina Ploscaru

Publication date 10 March 2005

Published in Journal of Applied Mathematics and Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf02936064

zbMATH Keywords

assignment problembipartite graphbipartite matching

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms (68W40) Programming involving graphs or networks (90C35)

Review text

The authors consider the following problem: given a matrix \(M\) with \(n\) rows and \(k\) columns, \(n\geq k\), choose an element from each column, such that no pair of elements is in the same row, and that the sum of all elements is minimal. When \(n=k\) the problem coincides with the assignment problem solved by the Hungarian algorithm, which is further equivalent to the problem of finding a minimal weighted perfect matching in a bipartite graph. An algorithm finding all solutions to the later problem in case \(n=k\) has been provided by \textit{K. Fukuda} and \textit{T. Matsui} [Networks 22, 461--468 (1992; Zbl 0762.90080)]. Here the authors generalize the algorithm of Fukuda and Matsui to the case when \(n>k\).

Recommendations

• The \(k\)-cardinality assignment problem
• scientific article; zbMATH DE number 841607
• Algorithm for the minimax assignment problem with a sparse rectangular matrix
• On Kuhn's Hungarian Method?A tribute from Hungary
• The Hungarian method for the assignment problem

Cites work

• Finding all minimum-cost perfect matchings in Bipartite graphs
• Finding all the perfect matchings in bipartite graphs
• scientific article; zbMATH DE number 5542185 (Why is no real title available?)
• scientific article; zbMATH DE number 1234600 (Why is no real title available?)
• scientific article; zbMATH DE number 2053216 (Why is no real title available?)
• scientific article; zbMATH DE number 1490953 (Why is no real title available?)
• scientific article; zbMATH DE number 3231692 (Why is no real title available?)
• Network flows. Theory, algorithms, and applications.

Cited in

(4)

• Combinatorial approaches to multiflow problems
• A combinatorial solution for bridge and torch problem
• An efficient approach for the rank aggregation problem
• scientific article; zbMATH DE number 912467 (Why is no real title available?)

This page was built for publication: Solving a combinatorial problem with network flows

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