The complexity of matching with bonds

DOI10.1016/0020-0190(89)90021-5zbMath0677.68053OpenAlexW2094880781MaRDI QIDQ1123620

Antonio Sassano, Manfred W. Padberg

Publication date: 1989

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(89)90021-5

zbMATH Keywords

computational complexityNP-hard problemmaximum-weight matchingrestricted matching problemsMatching with bonds

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Complexity of computation (including implicit computational complexity) (03D15)

Related Items (2)

A constrained matching problem ⋮ Assignment problem with conflicts

Cites Work

• Unnamed Item
• Unnamed Item
• Some simplified NP-complete graph problems
• The complexity of restricted spanning tree problems
• Some Matching Problems for Bipartite Graphs
• Matching, Euler tours and the Chinese postman

This page was built for publication: The complexity of matching with bonds