Constrained weighted matchings and edge coverings in graphs

DOI10.1016/S0166-218X(99)00052-9zbMath0930.05079WikidataQ126570203 ScholiaQ126570203MaRDI QIDQ1304484

Ján Plesník

Publication date: 9 February 2000

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

zbMATH Keywords

bipartite graphsassignment problemmaximum weight matchingmin-cost flowconstrained edge covering problem

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Related Items (14)

Solving the \(k\)-cardinality assignment problem by transformation ⋮ Lower bounds and exact algorithms for the quadratic minimum spanning tree problem ⋮ Edge covering problem under hybrid uncertain environments ⋮ Exact Algorithms for Edge Domination ⋮ A fuzzy model for NMT word alignment using quasi-perfect matching ⋮ Exact algorithms for edge domination ⋮ A unified approach to approximating partial covering problems ⋮ A refined exact algorithm for edge dominating set ⋮ On the transportation problem with market choice ⋮ Domination When the Stars Are Out ⋮ Parameterized measure \& conquer for problems with no small kernels ⋮ Parameterized algorithms for \(d\)-hitting set: the weighted case ⋮ Approximation algorithms for the submodular edge cover problem with submodular penalties ⋮ Fuzzy minimum weight edge covering problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Equivalence between the minimum covering problem and the maximum matching problem
• A shortest augmenting path algorithm for dense and sparse linear assignment problems
• The \(k\)-cardinality assignment problem
• A 1-matching blossom-type algorithm for edge covering problems
• An efficient algorithm for minimumk-covers in weighted graphs

This page was built for publication: Constrained weighted matchings and edge coverings in graphs