A generalized Hungarian method for solving minimum weight perfect matching problems with algebraic objective

DOI10.1016/0166-218X(79)90041-6zbMath0421.90057MaRDI QIDQ1133463

Ulrich Derigs

Publication date: 1979

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

weighted matching problemHungarian methodgeneral solution methodthreshold methodadmissible transformationsalgebraic objectivealgebraic perfect matching problemblossom algorithmbottleneck matching problemtotally ordered commutative monoid

Mathematics Subject Classification ID

Integer programming (90C10) Programming in abstract spaces (90C48) Semigroups (20M99)

Related Items

Duality for algebraic linear programming, Duality and admissible transformations in combinatorial optimization

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• TWO THEOREMS IN GRAPH THEORY
• Weakly admissible transformations for solving algebraic assignment and transportation problems
• An Efficient Implementation of Edmonds' Algorithm for Maximum Matching on Graphs
• An algebraic approach to assignment problems
• Matching, Euler tours and the Chinese postman
• Paths, Trees, and Flowers
• Maximum matching and a polyhedron with 0,1-vertices